刷题总结——树
总结刷题中遇到的与树有关问题
遍历问题
前中后序遍历
- 有递归与迭代两种写法
- 迭代时需要栈模拟，中序遍历单独注意写法（类似于模拟调用栈），后序遍历可以通过前序遍历+反转的方式实现
| 题目 | LC编号 | 注意事项 |
|---|---|---|
| 前序 递归 | 144 | 正常递归 |
| 前序 迭代 | 144 | 插入单个root后进行Stack模拟 pop之后插入右左 |
| 中序 递归 | 94 | 正常递归 |
| 中序 迭代 | 04.06 | 插入所有left后进行Stack模拟 假设pop的为根节点，插入右和右的所有leftmost节点 |
| 后序 递归 | 145 | 正常递归 |
| 后序 迭代 | 145 | 使用前序并且插入顺序变成左右，之后翻转 |
| 层序 迭代 | 102 | 使用queue容器模拟 |
步骤
对于遍历类题目，可以按照以下步骤：
- 要了解所求的答案从哪里来，并将其映射到前中后序遍历和层序遍历中的一种
- 之后就明确了使用DFS/BFS写法，需要引入哪些额外参数和全局变量：
- 前序：普通DFS
- 中序：带有额外input参数（前驱/后继节点）的DFS
- 后序：带有返回值的DFS，返回值用于根节点相关计算
- 层序：使用queue模拟实现的BFS
思考
此处引用灵神给的思考题，以及个人的思考
- 一般来说，DFS 的递归边界是空节点。在什么情况下，要额外把叶子节点作为递归边界？
- 如果把叶子节点作为递归边界，在写DFS的时候就要check加入的是否为空：
if (node->left) {
dfs(node->left, seq);
}
if (node->right) {
dfs(node->right, seq);
} - 有的时候可能要统计的是具体的某种性质的节点（比如左叶子/右叶子），这种情况下可能dfs函数需要使用叶子节点判断，然后进行相应计算
- 如果把叶子节点作为递归边界，在写DFS的时候就要check加入的是否为空：
- 在什么情况下，DFS 需要有返回值？什么情况下不需要有返回值？
- DFS返回值的作用是用于帮助根节点计算当前节点的结果，即当前目标值计算需要依靠左右子树dfs(root->left), dfs(root->right)各自的DFS返回值，如果不需要则可以不设置返回值
- 从DFS返回值到当前节点结果计算可以认为是自底向上“归”的过程，相当于后序遍历postorder
- 在什么情况下，题目更适合用自顶向下的方法解决？什么情况下更适合用自底向上的方法解决？
- 自顶向下pre-order：划分子问题并传入参数进入下层DFS，之后逐一遍历并且利用全局变量作最大值/最小值统计，dfs函数本身不需要返回值
- 自底向上post-order：汇总子节点DFS返回值，结合当前节点的值进行统计得到当前节点的答案，再利用全局变量作最大值/最小值统计，通常无需传入参数
- 一些复杂的问题中，DFS返回的和最终统计结果不一致，最终统计结果还需要通过全局变量来统计
- 在什么情况下，需要设计额外的变量作为DFS递归的额外参数？
- 有的问题需要在dfs中遍历到每个节点设置状态，并且前一个遍历的节点（前驱）的中间结果需要pass到后继节点使用，这个时候需要设计一些传参用来传递这种信息，通常是中序遍历，比如二叉树转链表/双向链表
- 自顶向下DFS需要维护统计量（LC题目298）
- 自底向上DFS中，其实是返回值代替了需要传下去的统计量，少一个入参多一个出参
- 这种题目可能还伴随设置dummy头节点的处理，用来简化问题
树形DP问题
树的直径：
- 注意全局变量ans和dfs返回值不一致的情况，ans计算直径/路径，dfs返回的是深度
- ans可以用全局变量存储，也可以用引用的形式作为dfs的传入参数
树形dp：
- 树dp并非具有重叠子问题，而是需要在子节点解决之后利用其状态进行当前节点的决策，这一步骤类似于dp中的状态转移
- 树dp问题有独立集问题和控制集问题，其实都可以归为子节点到父节点之间的状态转移（选/不选，染色），此时要求dfs返回的结果不是一个变量而是一组状态值,可以利用C++17的结构化绑定简化代码写法
LCA问题
二叉树LCA
LC题目235 236
二叉树LCA实际上也是一种后序遍历的递归，但是要注意的是递归函数返回值的定义，此处的定义设计为{p, q, LCA(p, q), none}中的一个；这里的设计是为了p和q一个在左一个在右的情况：
- 如果左右子树都返回值的时候，说明一个是p一个是q，那么LCA一定是root
- 如果只有一个子树有返回值，那么返回的一定是LCA节点，直接返回即可
BST是二叉树的特殊情况，如果是BST的话，可直接用值的范围作递归判断，简化了上述条件
一般树LCA
需要使用树上倍增的方法
路径问题
可以分成以下几类：
- 从根到叶节点的路径，其实就是DFS到叶节点结束，check条件是否满足（LC112 113）
- 不必从根节点开始，树中的几个节点有边相连即可：后序遍历，DFS函数记录当前子树中从根出发到某个结尾的值，求出左右子树返回值之后，再判断是否可以连接左右子树到根节点，通过全局变量更新结果（LC124 543）
- 方向从上到下的任意一个路径：前缀和问题，考虑结合hash的路径计算（LC437 面试题 04.12. 求和路径）
参考资料
- https://leetcode.cn/circle/discuss/K0n2gO/
- https://www.bilibili.com/video/BV1W44y1Z7AR/?vd_source=c80c62eac86a4ba033ab112349bbdd9f
- https://lfool.github.io/LFool-Notes/algorithm/二叉树路径相关技巧.html
- https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/solutions/2305895/mo-ban-jiang-jie-shu-shang-bei-zeng-suan-v3rw