阅读量:0
前言
从记录 三十五【二叉树基础和递归遍历】到记录 六十二【538.把二叉搜索树转换为累加树】28篇文章都是二叉树的章节。
所以总结的任务量有点大啊。但还是要做的。完成之后，开启新章节……
继续。
一、题目回顾
1-5：遍历方式模版题。
6- 14：确定遍历顺序。后序居多——先统计左右子树信息，回到本层处理后向上一层返回值。
15- 18 ：普通二叉树的修改：构造树、修改树、增加节点、删除节点。
19- 27 ：二叉搜索树的操作。
- 三十五【二叉树基础和递归遍历】：学会写 递归函数 的开端，解决以下问题：
- 什么是二叉树？二叉搜索树？平衡二叉树？平衡二叉搜索树？完全二叉树？满二叉树？
- 如何表示二叉树？（链表/左右孩子指针）
- 如何递归实现前中后序遍历？
- 记录 三十六【二叉树迭代遍历】：迭代实现的基础 模版。
- 独特的迭代实现：前后遍历是同一种；中序遍历是另一种。
- 统一的迭代模版：空指针标记法。数据结构：栈。
- 记录 三十七【二叉树层序遍历】：层序遍历（广度搜索）的 模版。
- 迭代实现：队列不为空，且处理新的一层是先记住当前队列里有多少个元素=该层有多个元素。
- 递归法：回溯。递归参数depth实现层数判断，“回归”时完成“回溯”过程。
- 记录 三十八【二叉树的层次遍历应用一及二叉树构建】和记录 三十九【二叉树层序遍历应用二】：层序模版的应用和给定数组形式的构建树。
- 数组形式构建树：一个节点下标i，左孩子的下标2i+1，右孩子的下标2i+2。创建使用结构：队列。销毁走后续遍历。
- 层序遍历模版应用题：
- 二叉树层序遍历，从底向上输出结果；
- 二叉树的右视图；
- 二叉树每一层的平均值；
- N叉树层序遍历；
- 二叉树中每一层的最大值；
- 填充节点的next指针：迭代实现使用层序模版；递归实现必须在题目的满二叉树的条件限制下。
- 填充节点的next指针 II ：迭代实现使用层序模版。
- 二叉树最大深度：层序遍历完成深度计数。（联动后面的深度问题）
- 二叉树最小深度：层序遍历过程中判断是否遇到叶子，及时break。（联动后面的深度问题）
- 记录 四十一【N叉树遍历】：以上遍历方式的扩展。
- 记录 四十【226.翻转二叉树】：交换左右孩子。重点确定遍历顺序。
- 递归实现：前序或者后序遍历；
- 迭代实现：前、后、层序。重点是注意交换后先处理谁？不要重复处理，二次交换后又换回去。
- 记录 四十二【101. 对称二叉树、100.相同的树、572.另一个树的子树】：同时操作两个树、确定遍历顺序：
- 递归参数一次性传入两个；
- 迭代实现：使用队或者栈同时放入两个要比较的节点。同时放入，同时取出。
- 确定好要比较的是谁和谁。
- 记录 四十三【最大、最小深度问题】：确定遍历顺序、回溯。
- 最大深度：后序遍历——借助左右子树的高度向上返回本层高度。前序遍历——depth进行回溯，如果比记录大，就更新。
- 最小深度：后序遍历——左右子树有一个是0，另一边高度+1；都不为0，取最小值+1.前序遍历——depth进行回溯，如果比记录小，就更新。
- 记录 四十八【513.找树左下角的值】：确定遍历顺序、回溯。
- 遍历顺序：无论哪一种都是先左后右，中节点不需要处理，所以那种遍历都可以；
- 树的左下角，需要最大深度。depth又涉及回溯。
- 记录 四十四【222.完全二叉树的节点个数】：确定遍历顺序。
- 后序遍历——借助左右子树的数量求和+1，向上一层返回；
- 利用完全二叉树的性质：左子树深度和右子树深度是否一样。位运算。
- 记录 四十五【110.平衡二叉树】：确定遍历顺序。
- 每个节点的子树都需要判断平衡。后序遍历。
- 记录 四十六【257. 二叉树的所有路径】：确定遍历顺序、回溯。
- 前序（唯一）：遇到叶子节点return上一层。
- 回溯：回到上一层，把下面加入path的元素弹出，减少就是回溯。
- 掌握递归就好。迭代的实现：前序遍历模版一个栈，放路径的一个栈。
- 记录 四十九【112. 路径总和】和【113. 路径总和ii】：和路径相关。确定遍历顺序、回溯。
- 思路一：搜集完整路径，终止条件的时候遍历求和；
- 思路二：边遍历，边减值。到终止条件时判断是否减到0.
- 遍历顺序：中节点没有处理逻辑。
- 记录 四十七【404.左叶子之和】：确定遍历顺序。
- 前序思路：2个参数，没有返回值。
- 后序思路：搜集左子树中左叶子之和+右子树中左叶子之和。
- 总结：前序实现更方便。
- 记录 五十【106.从中序与后序遍历序列构造二叉树】和【105.从前序与中序遍历序列构造二叉树】：构造一个树一定先找到中节点，再构造左子树，再构造右子树。拿着中节点分割数组。
- 划分区间时，保证区间始终左闭右开或左闭右闭。
- 最后使用下标分割，不用新开辟数组空间。
- 记录 五十一【654.最大二叉树】：构造树，和15.同理。
- 记录 六十一【108.将有序数组转换为二叉搜索树】：构建树。同15.理。
- 记录 五十二【617.合并二叉树】：修改树，借助其中一个树修改值。
- 和7. 中同时操作两个树借鉴。
- 记录 五十三【700.二叉搜索树中的搜索】：判断大小指明走向，无需遍历整个树。
- 记录 五十四【98.验证二叉搜索树】：中序遍历获得递增序列。双指针操作树。
- 双指针操作二叉搜索树的基本 模版。
- 记录 五十五【530.二叉搜索树的最小绝对差】：中序遍历获得递增序列。双指针操作树。
- 记录 五十六【501.二叉搜索树中的众数】中序遍历获得递增序列。双指针操作树，pre紧跟cur。
- 扩展普通二叉树求众数：遍历树获得值——数量映射。再用vec数组排序。对排序之后的数组遍历。
- 向上一层返回左子树中有无p或q，右子树中有无p或q。
- 在中间节点逻辑进行返回值判断。注意返回的是right或者left，不是root。
- 二叉搜索树可以指明方向，只进到一个子树中遍历。
- 记录 五十八【701.二叉搜索树中的插入操作】：利用大小指明方向，一定可以在叶子节点的位置添加。无需改动树的其他结构。
- 递归可以借助返回值或者使用双指针。
- 记录 五十九【450.删除二叉搜索树中的节点】：一定会改变树的结构。终止条件：当左右子树都不为空时稍微复杂。
- 扩展普通二叉搜索树删除操作：把当前节点和其右子树的最左端交换，直到交换到没有右子树。
- 记录 六十【669. 修剪二叉搜索树】：后序遍历。
- 先对左子树修剪；再对右子树修剪。回到中间判断向上一层返回哪边子树。
- 利用方向指明，修剪对应子树；
- 迭代：先调整根节点在范围之中。后修剪左右子树。
- 记录 六十二【538.把二叉搜索树转换为累加树】：确定遍历顺序。双指针法。
二、知识点整理
（1）遍历顺序选择原则
- 普通二叉树先考虑后序、再考虑前序、最后是中序。中序用的不多，能用前序的一般可以用后序。
- 后序：当需要从两个子树向上返回xxx信息时，最合适。（比如公共祖先）
- 二叉搜索树：中序遍历是有序递增序列。如果用不上有序递增序列，那么考虑后序遍历多。
（2）递归函数返回值确定原则
- bool类型：判断某个条件是否成立？/ 找xxx是否存在？
- void类型：有地方放结果就不需要返回值。或者只是遍历。
- TreeNode*或者int类型：向上一层返回子树？或者返回数值信息。很大概率用本层的left或right接住返回值。
（3）回溯体现
- 记录 三十七【二叉树层序遍历】的递归实现，depth回溯。
- 记录 四十三【最大、最小深度问题】前序遍历正向求深度，用到“回溯”，depth回溯。
- 记录 四十六【257. 二叉树的所有路径】前序遍历，路径元素弹出“回溯”。
- 记录 四十九【112. 路径总和】和【113. 路径总和ii】同理找路径，返回上一层时，遇到回溯。
- 记录 四十八【513.找树左下角的值】树的左下角需要是最大深度，所以又有回溯。
（4）终止条件总结
这个没有固定公式可以套用，但是不会确定终止条件时，可以从这里面选择尝试，看能不能通？
- if(cur == nullptr)当前节点为空；
- if(cur->left == nullptr && cur->right == nullptr)遇到叶子节点终止，属于在父节点判断子节点的情况。但是需要保证cur不为空。先判断是否不为空，再递归。举例：
（5）二叉搜索树思路
- 中序遍历性质；
- 大小性质指明方向。
- 后序遍历：修改二叉搜索树。
- 双指针法。
总结
由于本周事杂且多，所以总结篇迟迟未发。
题目回顾中可对照回想思路。
知识点总结：遇到问题后的思考方向。
接下来，继续“回溯”章节。
