树

1. 树

感谢代码随想录

1.1. 深度遍历

1.1.1. 递归

1. 递归结束条件
2. 当前递归操作
3. 对那些节点进行递归
4. 确定参数和返回值

1.1.2. 栈实现

深度遍历中存在先进后出，所以此处使用栈

1. 先序遍历，栈中先进后出，出栈顺序为3，2
   1. 中间节点
   2. 右节点
   3. 左节点
2. 中序遍历，当左节点与栈同时为空时，遍历结束
   1. 将所有左节点压入栈中
   2. 左节点为空时，将栈中节点弹出，处理中间节点
   3. cur= cur->right， 处理右节点
3. 后序遍历，参照1， 然后reverse

1.1.3. NULL/ bool表示

先序遍历，中左右，

1. 加入栈中顺序为右左中，标识当前节点需处理时在栈后加入一个NULL
2. 如果访问到NULL节点，需将下一节点弹出

1.2. 反转二叉树

反转二叉树

中序遍历不能反转二叉树，较为困难

1.3. 对称二叉树

对称二叉树

1. 确定返回条件
2. 当前节点比较左右字树是否相同
3. 比较的是节点的内侧(left的右， right的左)，节点的外侧

1.4. 树的最大深度

树的最大深度

1. 后序遍历： 回溯，从后面的节点结算，得到当前节点的结果
2. 前序遍历： 迭代，先计算当前节点，再依次计算后续节点，计算下一个节点时需要回溯

1.5. 树的最小深度

二叉树的最小深度

当节点的左右节点为都为NULL时，节点为叶子节点

1. 终止条件：节点为叶子节点时

2. 后序遍历，

   注意：此时depth != 左右子树最小的节点，有可能左右子树有空子树

   解决方法： 空子树设置深度初始值为最大值

1.6. 返回树的所有路径

树的所有路径

1. 路径的终止条件为达到叶子节点： 左右节点均为NULL;
2. 此时对left与right递归时需要对left, right做检查，同时中间节点的初始需要放在if判断之前；

两种方法回溯：

1. 使用vector存放路径，回溯时弹出最后一个元素；
2. 使用参数对路径修改，回溯时参数不变，等于回溯；

1.7. 左叶子之和

左叶子之和

1. 终止条件：
   1. 当前节点为空
   2. 是叶子节点
2. 当前逻辑：
   1. 获取左子树的做叶子之和
   2. 当左子树为左叶子时，单独计算
   3. 获取右子树的左叶子之和
3. 求和相加，返回

1.8. 路径之和

递归函数是否有返回值，分为三种情况

1. 需要对树的所有路径遍历且不用处理递归返回值， 递归函数没有返回值void
2. 需要对树的所有路径遍历且需要对递归返回值进行处理，递归函数有返回值int
3. 之搜索一条符合条件的路径，则需要返回返回值，返回值通常为bool

1.8.1. 找到路径即可

找到路径即可

1. 终止条件为找到叶节点
   1. 如果符合条件，返回true
   2. 不符合条件，返回false;
2. 如果左子树已经满足条件，返回true，不再搜索
3. 对右子树进行搜索

1.8.2. 找到所有可能的路径

找到所有可能的路径

1. 终止条件为找到叶节点
   1. 符合条件，加入结果集中
2. 找完左子树，再找右子树

1.9. 前序/中序创建二叉树

1. 终止条件：

   1. 数组为空时，返回NULL
   2. 数组为1个时，返回节点r

2. 处理逻辑：

   1. pre的第一个节点作为root节点
   2. 从中序in中找到与root相同的节点，以此为分割点，找到left ,right数组的长度
   3. 前序left, right与中序长度相同，所有区间为左开右闭

   	left	right
   pre	[leftPreorder+1, leftPreorder+1+left_size]	[ leftPreorder+1+left_size,rightPreorder]
   In	[ leftInorder, break_point]	[break_point+1, rightInorder]

3. 参数中包含数组分割节点

1.10. 创建最大树

1. 终止条件：可为叶子节点，也可以是NULL
2. 处理逻辑：
   1. 找到最大值索引，
   2. 使用索引分割两区间

1.11. 二叉搜索树

二叉搜索树

左子树 < 中间 < 右子树

由中间值比较，确定对左子树/ 右子树一棵树进行搜索

1.12. 验证二叉搜索树

左子树的所有值 < 中间 < 右子树的所有值， 所以不能单独比较 左节点 < 中间 < 右节点

使用中序遍历，左中右，比较结果

1. 中序遍历，得到数组，检查数组是否是从小到大
2. 中序遍历，保存遍历过程的做大值，保证遍历中的最大值< 当前值

1.13. 二叉树的最小差

二叉树所有数的最小值是相邻两个遍历节点的差值最小

1. 中序遍历，得到数组后，求数组相邻数据的差值

2. 中序遍历，保存上一个节点pre， 每次使用cur与pre做差值

   在中序结束后，将pre = cur， 将cur保存为下一变量的前一个节点

1.14. 找到最近公共祖先

最近公共祖先从下向上查询路径，后序遍历

1. 终止条件：
   1. 节点为NULL， 返回NULL
   2. 找到确定节点，返回true ,将result修改为当前路径；
2. 处理逻辑：
   1. 如果p，q是不同树，那么更新result结果；
   2. 如果只有q，在路径上，不更新result;(因为可能出现q是p的父节点，由终止条件2修正)

1.15. 二叉搜索树的最近公共祖先

二叉搜索树

二叉树有序，所以p,q的祖先节点位于[p,q]之间，且最近公共祖先是其遍历中的第一个，也只有这一个满足[p,q]条件

1.16. 二叉搜索树的插入

插入

1. 终止条件： 遇到空节点，新建一个节点，并加入在parent节点左/右
2. 操作逻辑：
   1. val大于节点，进入右子树
   2. val小于节点，进入左子树

也可以不使用parent节点，终止条件中返回创建的节点，在操作时将返回的节点插入

1.17. 二叉搜索树的删除

删除

终止条件：删除时如果左右子树都在，需要将左子树放在右子树的最左节点的最左侧

1.18. 二叉树的修剪

二叉树的修剪

1. 终止条件： 如果root==NULL时，返回NULL;
2. 处理逻辑：
   1. 中： 如果root < left ,修建左子树，将左子树合适节点代替root返回，反之亦然
   2. 左： 对左子树修剪，返回结果赋值给root的左子树
   3. 右：同上

1.19. 有序数组->二叉搜索树

有序数组构建二叉搜索树

1. 终止条件： 节点为空
2. 处理逻辑：
   1. 有序数组的中间位置为根节点
   2. 左子树，调用区间构建左子树
   3. 右同上

1.20. 二叉搜索树求和

二叉搜索树转换为累加树

1. 终止条件： ~
2. 处理逻辑：
   1. 二叉树有序，选择右中左遍历
   2. 每次遍历时，需使用pre保存前一节点的累加和