二叉树的基本性质
思路
- 二叉搜索树的基本性质，二叉树前中后序遍历的特性，完全二叉树的性质
- 从前，中遍历或中，后遍历能够推出二叉树
- 关于节点数量的规律：设非空二叉树中度为0、1和2的结点个数分别为n0、n1和n2，则有 n0 = n2 + 1
- 即叶子结点比二分支结点多一个
例题
100、相同的树（两边dfs）
101、对称二叉树（两边dfs）
104、二叉树的最大深度（dfs）
124、二叉树的最大路径和
- 最大路径和的两种情况：
- 1、从当前节点出发，只走左子树或右子树
- 2、从左子树的某一处出发，经过当前节点，然后到达右子树的某一处
- 问题就转化为如何用同一套代码能够将这两种情况都包含，或是说二者的共同点在哪儿
- 思路：为什么会出现只走左/右子树，是因为走左/右子树只能得到小于等于0的结果；因此得到一个思路，在寻找最大路径和的时候，左子树给出的结果应该是
max(0,dfs(root -> left)) - 整体逻辑：设置全局变量maxn，设最开始的
maxn为root -> val（如果nullptr就返回0） - 分别对各个点进行左右遍历，得到
left = max(0, dfs(root -> left))和right = max(0, dfs(root -> right)) - 然后，得到
max1 = left + right + root -> val，maxn = max(max1, maxn)，最后，当前函数需要返回root -> val + max(left, right)（因为当前节点又会被上一层给调用） - 这种逐层递归的好处，是可以枚举每个节点遇到上述情况时候的取值，从而得到全体最大值
236、二叉树的最近公共祖先
- 先判断当前的节点是不是目标节点之一（或者是不是nullptr），如果是就直接返回
- 否则就判断左边和右边，如果左边是空的，那就证明必然是右边，反之也是一样
- 如果两边都不是空的话，就代表两个节点在当前节点的两侧，直接返回当前节点
257、二叉树的所有路径（字符串+经典的dfs）
572、另一棵树的子树（子树的定义）
- 子树的定义：对于一个节点，二者都是null，ok；原树有、新树没有，或者原树没有，新树有，error
543、二叉树的直径
- 二叉树的最长直径的两种情况
- 1、从当前节点出发，只走左子树或右子树
- 2、从左子树的某一处出发，经过当前节点，然后到达右子树的某一处
- 和687，124都是一模一样的套路
617、合并二叉树（DFS，需要注意空节点）
653、两数之和 IV（输入BST）（剑指offerII 56 二叉搜索树中两个结点之和）：哈希表+前序遍历即可
671、二叉树中第二小的节点（读题仔细，dfs解决，老套路了）
687、最长同值路径
- 二叉树的最长同值路径的两种情况
- 第一种：从该点出发，只走左子树或右子树
- 第二种：从左子树的某一处出发，经过该节点，然后到达右子树的某一处
- 和543，124都是一模一样的套路
- 需要注意一点的是，要传入上一个结点的number，通过当前的root->val和number来判断要返回的是0还是其他的
814、二叉树剪枝（自底向上的遍历，和之前一道题很像，忘了是那一道，后续看看）
- 剑指offer II 047.二叉树剪枝（一模一样的）
951、翻转等价二叉树（感觉和验证两个二叉树是否相等一样，都是比较左右节点的题目）
剑指offer 26 树的子结构
- 对于每个点都判断是否为目标二叉树
- 一定要注意树的子结构和树的子树是不一样的：
- 如果是子树，就必须要求两棵树上所有的结点都要能够对上（原树为空，目标树必须为空；原树有结点，目标树也得有结点）（目标树为空，原树必须也为空；目标书有节点，原树必须也有结点）
- 如果是子结构，只要目标树有的原树都有，就行了（原树为空，目标树必须为空；原树有结点，目标树可以没有结点）（如果目标树为空，那么原来的树有没有结点都无所谓；如果目标树有结点，原树必须也有结点）
层序遍历
思路
- 树的层序遍历，即广度优先搜索；或者在层序遍历的时候，添加一些其他的操作
模板
- 建立一个queue，最开始将第一个root点放入队列，进行我们想要的操作（求最大值、平均值、最左边的数）
- 注意此时一开始是用一个node记录此时的queue.front()，接着把这个点从队列中pop
- 操作完后，就把该点的左右结点给放入队列中；递归循环上述操作
- 踩坑：for循环中要用一个size记录初始队列的大小，因为随着后续的元素不断放入，size会改变的
- 或者从后往前遍历也是可以的
例题
102、二叉树的层序遍历（层序遍历）
103、二叉树的锯齿形层序遍历（层序遍历；根据深度反转数组）
111、二叉树的最小深度（用层序遍历记录floor；也可以用递归求解）
199、二叉树的右视图（层序遍历；每次只取最后一个数）
222、完全二叉树的节点个数（层序遍历；遇到nullptr就break）
429、N叉树的层序遍历（层序遍历）
513、找树左下角的值（层序遍历，记录每次出现的第一个值）
515、在每个树行中找最大值（层序遍历；记录行max）
637、二叉树的层平均值（层序遍历；求avg）
662、二叉树的最大宽度（用两个队列来实现层序遍历；或者用一个新的结构体Node，同时记录节点的val和节点的指针，放入左节点就是* 2，放入右节点就是 *2 + 1；最后注意防越界，用unsigned long long即可）
958、二叉树的完全性检验（层序遍历；根据完全二叉树的性质，一旦遇到nullptr，后面就不应该有节点了，否则就不是完全二叉树；用一个flag来表示是否遇到了nullptr）
1609、奇偶树（层序遍历；根据奇偶做不同的处理）
面试题 04.03、 特定深度节点链表（层序遍历生成链表）
剑指offer 32、从上到下打印二叉树（层序遍历）
剑指offer II 044.二叉树每层的最大值
剑指offer II 045.二叉树最底层最左边的值
剑指offer II 046.二叉树的右侧视图
前中后序遍历
思路
- 需要对树进行根左右，左根右，左右根的遍历，并且在每次遍历的时候添加其他操作
模板
- 遍历一般有两种方式来实现，第一种是递归，第二种是用栈模拟递归（挖坑：第三种遍历mirror遍历不会）
例题
94、二叉树的中序遍历（递归/非递归版）
98、验证二叉搜索树
- 这道题是用到了二叉搜索树的性质+中序遍历。即对于每棵树，根节点是大于左子树的节点的，右子树的节点是大于根节点的
- 然后联想到中序遍历是左根右的，所以就一方面维护一个pre节点，另一方面左根右的遍历，走完左子树，pre就变为左子树中的最大值（即左子树的右子树其中一个值），和根节点比较；走完根节点，pre就变为根节点，和右子树的左子树的最小值（即右子树的左子树其中一个值）进行比较）
- 这就是中序遍历的高深之处，始终维护着pre为一部分的最大值
- 这道题的做法无非就是中序遍历的变种（第一种是每次遍历都维护前面一个节点，第二种是递归得到全部的数组，第三种是stack维护前一个节点）
105、从前序遍历与中序遍历构造二叉树
- 模板题
- 关于右边界的问题，是否要取到右边界都是可以选择的，关键是你怎么写（我的做法中右边界是不可取值的）
106、从中序遍历与后序遍历构造二叉树
- 同105一样的思路，类似的题还有剑指 offer07
144、二叉树的前序遍历（递归/非递归版）
145、二叉树的后序遍历（递归/非递归版；非递归实现思路，后序遍历是左右根，那么就相当于是根右左反过来，所以只要求得根右左，反转后便是结果）
589、N叉树的前序遍历（递归/非递归版）
590、N叉树的后序遍历（递归/非递归版）
872、叶子相似的树（非常巧妙地中序遍历输出叶子，然后对比）
剑指 offer36（挖坑）
原创题：二叉树的下一个节点（中序遍历；如果有右子树，就往右子树下面找，否则就往上找）
二叉搜索树
思路
- 二叉搜索树的性质：中序遍历得到的数组是依次递增的，右左根得到的数组是依次递减的，当前节点的数字是大于左边而小于右边的
模板
- 中序遍历或者是右左根遍历，都可以用递归或stack来实现
例题
95、不同的二叉搜索树 II（用递归分别求出左右两个子树，然后用两层循环嵌套生成二叉树）
98、验证二叉搜索树（利用二叉搜索树的性质，中序遍历的递归和非递归版，或者把中序遍历一遍二叉树，然后逐个逐个看是否大于前一个）
99、恢复二叉树（也是利用二叉树搜索树和中序遍历的性质，但是其中利用r1和r2的方法真的很绝，建议好好看看）
108、将有序数组转换为二叉搜索树（经典传递数组和数组边界，然后递归）
109、有序链表转换二叉搜索树（经典利用二叉搜索树的性质，取中间数作为节点，然后递归left和right）
230、二叉搜索树中第k小的元素
- 中序遍历，每次得到元素的时候修改k，当k为0的时候return
- 或者dfs，本质上也是中序遍历
235、二叉搜索树的最近公共祖先
- 通过大小判断接下来遍历那一边的子树
450、删除二叉树中的节点（非常经典的题目，既可以把左子树接到右子树的最左边的节点上，也可以把右子树接到左子树最右边的节点上）
530、二叉搜索树的最小绝对差（二叉搜索树的性质，中序遍历）
538、把二叉搜索树转换为累加树（1038.把二叉搜索树转换为累加树，剑指offer II 054.所有大于等于节点的值之和）
- 这道题的思路很巧妙：用的是反向的中序遍历，先遍历右边，再处理root，最后遍历左边（其中还用了一个全局变量来维护右子节点的最大值）
- 思路和实现上都比较简单，但是很难想到如此的巧妙
- 而我的思路：
- 对于一个节点本身来说，右子节点是用来给自身赋值的，所以，如果能往右边走，当前的值就是右边，就继续递归下去
- 如果不能，那就继承父类给的base（具体参考代码）
- 而对于左节点，如果左节点不能走，那以本节点为根节点的树的最大值就是root->val
- 如果能走，那就返回递归的左节点
669、修建二叉搜索树（利用二叉搜索树的性质，如果当前的值小于low，就把左子树砍掉，返回右子树；如果当前的值大于high，就把右子树砍掉，返回左子树）
701、二叉搜索树中的插入操作（二叉搜索树的性质）
783、二叉搜索树节点最小距离（同上）
897、递增顺序搜索树（利用二叉搜索树性质中序遍历建树）
938、二叉搜索树的范围和（利用二叉搜索树性质）
剑指offer 54、 二叉搜索树的第k大节点
- 非递归的做法（右左根依次遍历，得到便是依次递减的数列，同时更新k值，递减到0为止）
- 递归的做法（递归实现右左根遍历）
- 本质上就是倒过来的先序遍历
剑指offer 33、二叉搜索树的后序遍历
经典传递数组边界：（我的做法）
对于一个二叉搜索树的后序遍历来说，左右根，所以从最后一个结点往前会存在一部分B，使得B中所有的元素都大于根节点
，剩下的部分A则存在所有的元素都小于根节点，由此可以调整数组的边界，使用递归可以实现判断
正规的做法是：
- 埋坑（第二种做法确实看不懂….）
剑指offer 36、二叉搜索树与双向链表
- 这道题背就完事了
- 这道题需要好好的看一遍题解去思考消化
面试题04.02、最小高度树（利用二叉搜索树性质，每次去数组中间的值作为节点的值）
平衡二叉树
110、平衡二叉树（自底向上的思考，如果当前的树不是，那上面的树也不是了，就往上走即可）
- 这里有个小trick，就是如果当前节点确定了不是平衡二叉树，那么就返回-1
其他
96、不同的二叉搜索树（动态规划，每次都枚举左边可能有多少个，右边可能有多少个，然后相乘得到结果）
112、路径总和（经典dfs，发现targetsum为0，并且是叶子节点，就返回）
113、路径总和II（经典dfs，需要注意的就是每次放入元素后，在退出函数的时候要把元素pop_back；理解上就是，你左边走完了，当然要退回一步，然后让右边继续往下走）
114、二叉树展开为链表（这里可以延伸一下变为中序遍历，变为后序遍历的时候该咋写）
116、填充每个节点的下一个右侧节点指针
- 对于每个点，用solve（dfs函数）不断的递归
117、填充每个节点的下一个右侧节点指针II
- 依次遍历每一层，然后记录每个点的前一个点nodepre，让nodepre的next指向自己，然后再把自己变为nodepre
129、求根节点到叶节点数字之和（经典dfs）
- 镜像：剑指offer II 049.从根节点到叶节点的路径数字之和
- 可以选择用一个res记录总和，也可以每次都将相加后返回
226、翻转二叉树（模拟）
剑指offer27 二叉树的镜像
- 可以使用一个节点来实现翻转
404、左叶子之和
- 方法一：用flag来判断是不是左节点
- 方法二：对于每个节点，都判断他的左节点，然后相加
543、二叉树的直径
- 遍历每个节点，每次的最大值都是左值加上右值（最大值用全局变量来维护）
863、二叉树中所有距离为 K 的结点
- 用哈希表实现dfs，真的巧妙啊！！！！！
993、二叉树的堂兄弟节点
- 比较层数和父母即可
剑指offer 34 二叉树中和为某一值得路径
- dfs+记录状态
字节面试题：二叉树中任意两节点之间的最短路径（给定两点，求它们之间的最短路径）
- 思路：先找到两个点的最近公共祖先，然后再用dfs就该祖先到两点距离，最后相加
nowcoder经典笔试题
- 找到二叉树中的最大搜索二叉子树
总结
- 深搜 -> dfs递归
- 广搜 -> 层序遍历队列
