树形递归技巧

last modify

• 前言

• 后序遍历的递归技巧

  • 示例 1: 二叉树的高度

  • 示例 2: 判断是否为平衡二叉树/搜索二叉树/完全二叉树

  • 示例 3: 二叉树中的最大路径和

  • 示例 4: 打家劫舍 III

• 前序遍历的信息传递

  • 示例: 判断完全二叉树

  • 示例: 路径总和

• 更多相关问题

• 参考资料

前言

• 二叉树的三种遍历方式 (前序, 中序, 后序) 代表了三种典型的递归场景;

  def dfs(node):
      if node is None: return
      
      ...  # 前序
      dfs(node.left)
      ...  # 中序
      dfs(node.right)
      ...  # 后序

• 这三种遍历方式的主要区别在于遍历到当前节点时, 已知节点的位置不同, 以根节点为例:

  • 前序遍历到根节点时, 其他节点都未知;

  • 中序遍历到根节点时, 遍历完了整棵左子树;

  • 后序遍历到根节点时, 已经遍历完了所有子节点;

• 可见,

  • 前序遍历是自顶向下的递归; 如果当前节点需要父节点的信息时, 就用前序遍历;

  • 后序遍历是自底向上的递归; 如果当前节点需要子节点的信息时, 就用后序遍历;

  • 中序遍历比较特殊, 可以认为它是二叉树特有的, 比如对一棵多叉树, 中序遍历就无从谈起, 所以中序遍历主要用在那些利用了二叉树特殊性质的情况, 比如二叉搜索树;

• 我们使用递归的一个关键, 就是希望将问题分解为子问题后再逐步解决,

  • 这一点非常契合后序遍历的方式, 即从子树的解, 递推全局的解, 所以后序遍历的问题是最多的;

  • 此时可以把这种在树上进行的递归看作是一种特殊的动态规划, 即树形 dp;

    递归与动态规划的关系

• 本篇介绍的技巧, 简单来说就是如何结构化处理这些子问题的解, 这个方法可以用于所有需要自底向上进行递归的问题;

后序遍历的递归技巧

自底向上的递归技巧, 树形 dp 等

• 记 dfs(x) 模板如下:

  from dataclasses import dataclass
  
  @dataclass
  class Info:
      ...  # default
  
  def dfs(x) -> Info:
      if x is None: return Info()
  
      l_info = dfs(x.left)
      r_info = dfs(x.right)
      x_info = get_from(l_info, r_info)
      return x_info

• 考虑计算出当前节点的答案需要从左右子树获得哪些信息, 并假设已知, 记 l_info 和 r_info;

• 利用 l_info 和 r_info 构造出当前节点应该返回的信息 x_info;

• 注意空树返回的信息, 即 Info 的默认值;

• 为了可读性, 推荐使用结构体 (python 中推荐使用 dataclass) 来保存需要的信息;

• 进一步的, 最终生成的 x_info 不一定都会与 x 有关, 此时需要分与 x 有关的答案和与 x 无关的答案进行讨论, 并取其中的最优解 (详见示例 3 和 4);

示例 1: 二叉树的高度

104. 二叉树的最大深度 - 力扣（LeetCode）

• 二叉树 x 的高度等于左右子树高度中的较大值 +1;

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        
        def dfs(x):
            if x is None: return 0

            l, r = dfs(x.left), dfs(x.right)
            return max(l, r) + 1
        
        return dfs(root)

本题比较简单, 故简化了模板;

示例 2: 判断是否为平衡二叉树/搜索二叉树/完全二叉树

98. 验证二叉搜索树 - 力扣（LeetCode） 110. 平衡二叉树 - 力扣（LeetCode） 958. 二叉树的完全性检验 - 力扣（LeetCode）

• 搜索二叉树: 对每个节点, 其值大于左子树的最大值，小于右子树的最小值;

• 平衡二叉树: 对每个节点, 其左右子树的高度差 <= 1;

• 完全二叉树, 这里给出两种判断条件:

  • 条件1:

    • 左右子树都是满二叉树，且高度相同, 即本身是满二叉树；

    • 左右子树都是满二叉树，且左子树的高度+1；

    • 左子树是满二叉树，右子树是完全二叉树，且高度相同；

    • 左子树是完全二叉树，右子树是满二叉树，且左子树的高度+1；

      满二叉树: 左右子树的高度相同, 且都是满二叉树;

  • 条件2, 该方法需要前序遍历进行预处理 (详见下一节: 前序遍历的信息传递):

    • 记根节点 id 为 1；若父节点的 id 为 i，则其左右子节点分别为 2*i 和 2*i+1；

    • 如果是完全二叉树则有 max_id == n，其中 n 为总节点数；

• 以下为合并实现

class Solution:
    def isXxxTree(self, root: TreeNode) -> bool:

        from dataclasses import dataclass

        @dataclass
        class Info:
            height: int = 0               # 树的高度
            max_val: int = float('-inf')  # 最大值
            min_val: int = float('inf')   # 最小值
            is_balance: bool = True       # 是否平衡二叉树
            is_search: bool = True        # 是否搜索二叉树
            is_full: bool = True          # 是否满二叉树
            is_complete: bool = True      # 是否完全二叉树
        
        def dfs(x):
            if not x: return Info()

            l, r = dfs(x.left), dfs(x.right)

            # 利用左右子树的info 构建当前节点的info
            height = max(l.height, r.height) + 1
            max_val = max(x.val, l.max_val, r.max_val)
            min_val = min(x.val, l.min_val, r.min_val)
            is_balance = l.is_balance and r.is_balance and abs(l.height - r.height) <= 1
            is_search = l.is_search and r.is_search and x.val > l.max_val and x.val < r.min_val
            is_full = l.is_full and r.is_full and l.height == r.height
            is_complete = is_full \
                or l.is_full and r.is_full and l.height - 1 == r.height \
                or l.is_full and r.is_complete and l.height == r.height \
                or l.is_complete and r.is_full and l.height - 1 == r.height
            
            return Info(height, max_val, min_val, is_balance, is_search, is_full, is_complete)
        
        return dfs(root).xxx  # 根据具体问题确定返回值

示例 3: 二叉树中的最大路径和

124. 二叉树中的最大路径和 - 力扣（LeetCode）

• 根据最大路径和是否经过 x 节点分两种情况;

  • 如果不经过 x 节点, 那么 x 中的最大路径和等于左右子树中最大路径和中的较大值;

  • 如果经过 x 节点, 那么 x 的最大路径和等于左右子树能提供的最大路径之和, 再加上当前节点的值;

  • 取两者中的较大值;

• 综上, 需要记录的信息包括, 当前节点能提供的最大路径, 当前的最大路径;

  • 所谓 "当前节点能提供的最大路径", 即从该节点向下无回溯遍历能得到的最大值; 假设每个节点能提供的路径都是 1, 那么这个最大路径就是树的高度;

  • 因为节点值存在负数, 这是一个容易出错的点 (详见代码);

• 从本题可以看到, 模板并不能解决问题, 只是减少了问题以外的思考, 即如何将思路转换为代码.

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:

        from dataclasses import dataclass

        @dataclass
        class Info:
            # 易错点: 因为存在负值, 所以初始化为负无穷 (最小值为 -1000)
            h: int = -1001  # 当前节点能提供的最大路径
            s: int = -1001  # 当前节点下的最大路径
        
        def dfs(x):
            if not x: return Info()

            l, r = dfs(x.left), dfs(x.right)
            # 利用左右子树的信息, 计算当前节点的信息
            h = x.val + max(l.h, r.h, 0)  # 易错点: 如果左右子树能提供的最大路径是一个负数, 则应该直接舍去
            s_through_x = x.val + max(l.h, 0) + max(r.h, 0)  # 易错点: 同上
            # 因为 h 和 s_through_x 都和当前节点有关, 所以必须包含当前节点
            s = max(l.s, r.s, s_through_x)  # 但是最终结果不一定包含 x, 需要取最优解
            return Info(h, s)
        
        return dfs(root).s

示例 4: 打家劫舍 III

337. 打家劫舍 III - 力扣（LeetCode）

• 树形 dp，就是否抢劫当前节点分两种情况讨论;

class Solution:
    def rob(self, root: TreeNode) -> int:

        from functools import lru_cache

        @lru_cache
        def dfs(x):
            # 空节点, 不抢
            if not x: return 0
            # 叶节点, 必抢
            if not x.left and not x.right: return x.val

            # 不抢当前节点, 抢左右子节点
            r1 = dfs(x.left) + dfs(x.right)
            # 抢当前节点, 跳过左右子节点, 抢子节点的子节点
            r2 = x.val
            if x.left:  # 非空判断
                r2 += dfs(x.left.left) + dfs(x.left.right)
            if x.right:  # 非空判断
                r2 += dfs(x.right.left) + dfs(x.right.right)
            
            return max(r1, r2)
        
        return dfs(root)

前序遍历的信息传递

• 后序遍历中, 父节点获取子节点的信息很自然, 直接在函数体内接收递归的结果即可;

• 前序遍历中, 子节点想要获取父节点的信息就不能这么做, 一般的方法是通过参数传递;

  from dataclasses import dataclass
  
  @dataclass
  class Info:
      ...  # default
  
  def dfs(x, f_info) -> Info:
      if x is None: return Info()
  
      f_info = process(f_info)  # 利用父节点的信息进行预处理
  
      l_info = dfs(x.left, f_info)
      r_info = dfs(x.right, f_info)
  
      x_info = get_from(l_info, r_info)
      return x_info

示例: 判断完全二叉树

958. 二叉树的完全性检验 - 力扣（LeetCode）

• 思路:

  • 记根节点 id 为 1；若父节点的 id 为 i，则其左右子节点分别为 2*i 和 2*i+1；

  • 如果是完全二叉树则有 max_id == total_cnt，其中 total_cnt 为总节点数；

• 这里子节点的 id 就需要通过父节点的 id 来计算;

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        
        self.total_cnt = 0
        self.max_id = 0

        def dfs(x, node_id):
            if not x: return

            self.total_cnt += 1
            self.max_id = max(self.max_id, node_id)
            dfs(x.left, node_id * 2)
            dfs(x.right, node_id * 2 + 1)

        dfs(root, 1)
        return self.total_cnt == self.max_id

示例: 路径总和

112. 路径总和 - 力扣（LeetCode）

• 问题简述:

  • 判断树中是否存在 根节点到叶子节点 的路径和等于 targetSum;

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root: return False

        self.ret = False

        def dfs(x, s):
            if self.ret or not x:
                return

            s += x.val
            if x.left is None and x.right is None:
                self.ret = s == targetSum
                return

            dfs(x.left, s)
            dfs(x.right, s)
            s -= x.val  # 回溯
        
        dfs(root, 0)
        return self.ret

更多相关问题

algorithms/树形递归

参考资料

• 动态规划——树形DP_浅梦曾倾 - CSDN

• 从五道题来看树形DP_数学家是我理想 - CSDN

• [视频] 二叉树的递归套路_左程云算法教程 (p47) - B站

  • [文字] 树型递归思想_LiJiaLe - CSDN