刷题总结——树

总结刷题中遇到的与树有关问题

遍历问题

前中后序遍历

• 有递归与送代两种写法
• 迭代时需要栈模拟，中序遍历单独注意写法（类似于模拟调用栈），后序遍历可以通过前序遍历+反转的方式实现

步骤

对于遍历类题目，可以按照以下步骤：

• 要了解所求的答案从哪里来，并将其映射到前中后序遍历和层序遍历中的一种
• 之后就明确了使用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 需要有返回值？什么情况下不需要有返回值？
  • DFS返回值的作用是用于帮助根节点计算当前节点的结果，即当前目标值计算需要依靠左右子树dfs(root->left), dfs(root->right)各自的DFS返回值，如果不需要则可以不设置返回值
  • 从DFS返回值到当前节点结果计算可以认为是自底向上“归”的过程，相当于后序遍历postorder
• 在什么情况下，题目更适合用自顶向下的方法解决？什么情况下更适合用自底向上的方法解决？
  • 自顶向下pre-order：划分子问题并代入参数进入下层DFS，之后逐一遍历并且利用全局变量作最大值/最小值统计，dfs函数本身不需要返回值
  • 自底向上post-order：汇总子问题解，得到当前的解，通常无需传入参数
  • 一些复杂的问题，本身属于自底向上的方法，但是还需要通过全局变量来计算结果，即dfs返回的和最终统计结果不一致
• 在什么情况下，需要设计额外的变量作为DFS递归的额外参数？
  • 有的问题需要在dfs中遍历到每个节点设置状态，并且前一个遍历的节点（前驱）的中间结果需要pass到后继节点使用，这个时候需要设计一些传参用来传递这种信息，通常是中序遍历，比如二叉树转链表/双向链表
  • 自顶向下DFS需要维护统计量（题目298）
  • 自底向上DFS中，其实是返回值代替了需要传下去的统计量，少一个入参多一个出参
  • 这种题目可能还伴随设置dummy头节点的处理，用来简化问题

树型DP问题

树的直径：

• 注意全局变量ans和dfs返回值不一致的情况，ans计算直径/路径，dfs返回的是深度

• ans可以用全局变量存储，也可以用引用的形式作为dfs的传入参数

• 树dp并非具有重叠子问题，而是需要在子节点解决之后利用其状态进行当前节点的决策，这一步骤类似于dp中的状态转移

• 树dp问题有独立集问题和控制集问题，其实都可以归为子节点到父节点之间的状态转移（选/不选，染色），此时要求dfs返回的结果不是一个变量而是一组状态值,可以利用C++17的结构化绑定简化代码写法

LCA问题

二叉树LCA

一般树LCA

路径问题

结合hash的路径计算