[Vssue]二叉树总结篇.md

[youngyangyang04]

https://www.programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E6%80%BB%E7%BB%93%E7%AF%87.html

[yfabc123]

复习

[Du1in9]

二叉树的遍历方式

• 深度优先遍历：递归遍历、迭代遍历、统一迭代法
• 广度优先遍历：层序遍历

二叉树的属性

1. 二叉树：是否对称。后序，比较的是根节点的左子树与右子树是不是相互翻转
2. 二叉树：求最大深度。后序，求根节点最大高度就是最大深度，通过递归函数的返回值做计算树的高度
3. 二叉树：求最小深度。后序，求根节点最小高度就是最小深度，注意最小深度的定义
4. 二叉树：求有多少个节点。后序，通过递归函数的返回值计算节点数量
5. 二叉树：是否平衡。后序，注意后序求高度和前序求深度，递归过程判断高度差
6. 二叉树：找所有路径。前序，方便让父节点指向子节点，涉及回溯处理根节点到叶子的所有路径
7. 二叉树：求左叶子之和。后序，必须三层约束条件，才能判断是否是左叶子。
8. 二叉树：求左下角的值。顺序无所谓，优先左孩子搜索，同时找深度最大的叶子节点。
9. 二叉树：求路径总和。顺序无所谓，递归函数返回值为 bool 类型是为了搜索一条边，没有返回值是搜索整棵树。

二叉树的修改与构造

1. 翻转二叉树。前序，交换左右孩子
2. 构造二叉树。前序，重点在于找分割点，分左右区间构造
3. 构造最大的二叉树。前序，分割点为数组最大值，分左右区间构造
4. 合并两个二叉树。前序，同时操作两个树的节点，注意合并的规则

二叉搜索树的属性

1. 二叉搜索树中的搜索。二叉搜索树的递归是有方向的
2. 是不是二叉搜索树。中序，相当于变成了判断一个序列是不是递增的
3. 求二叉搜索树的最小绝对差。中序，双指针操作
4. 求二叉搜索树的众数。中序，清空结果集的技巧，遍历一遍便可求众数集合
5. 二叉搜索树转成累加树。中序，双指针操作累加

二叉搜索树的修改与构造

1. 二叉搜索树中的插入操作。顺序无所谓，通过递归函数返回值添加节点
2. 二叉搜索树中的删除操作。前序，想清楚删除非叶子节点的情况
3. 修剪二叉搜索树。前序，通过递归函数返回值删除节点
4. 构造二叉搜索树。前序，数组中间节点分割

二叉树公共祖先问题

1. 二叉树的公共祖先问题。后序，回溯，找到左子树出现目标值，右子树节点目标值的节点。
2. 二叉搜索树的公共祖先问题。顺序无所谓，如果节点的数值在目标区间就是最近公共祖先