数据结构与算法 / 系统课时

用递归返回值处理二叉树问题

用递归返回值处理二叉树问题

二叉树递归最容易写乱的地方,是把“父节点传给当前节点的信息”和“当前子树返回给父节点的结果”混在一起。把这两个方向分开后,很多深度、路径、统计和最优值问题都会变成稳定的递归接口设计。

学习目标

  • 区分向下传递的路径状态与向上返回的子树结果
  • 能为二叉树递归设计清晰的参数和返回值
  • 能判断答案应由返回值直接得到,还是需要额外汇总

先决定信息往哪个方向流

设计递归函数前,不要先写 dfs,先回答两个问题:当前节点需要从父节点知道什么,以及父节点需要从当前子树得到什么。

向下传递的信息通常与“从根到当前节点的路径”有关,例如当前深度、路径和、剩余目标值、路径上的最大值。这类状态放在递归参数里,因为它由父节点计算后交给子节点。

向上返回的信息通常描述“以当前节点为根的整棵子树”,例如子树高度、节点数、是否平衡、子树最大值。这类结果放在 return 中,因为父节点要等左右子树都算完后再组合。

二叉树递归中向下状态与向上返回值

用一个递归同时处理上下行信息

以“好节点”为例:若从根到当前节点的路径上,没有任何节点值大于当前节点,则当前节点是好节点。为了判断当前节点,需要知道路径最大值,因此 path_max 必须向下传递;而父节点只关心当前子树一共有多少个好节点,因此递归函数返回计数。

递归接口可以直接写成:dfs(node, path_max) -> 当前子树中的好节点数量。当前节点只做三件事:判断自己是否满足条件、更新传给孩子的路径最大值、把左右子树返回的数量相加。

完整实现并验证

下面的树对应层序数据 3, 1, 4, 3, null, 1, 5。其中根节点 3、左子树中的 3、右子节点 4 和节点 5 都是好节点,因此答案为 4。

python
class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def count_good_nodes(root):
    if root is None:
        return 0

    def dfs(node, path_max):
        if node is None:
            return 0

        # path_max 来自父节点,描述根到当前节点之前的路径状态。
        is_good = 1 if node.val >= path_max else 0
        next_max = max(path_max, node.val)

        # 返回值只描述当前子树,供父节点继续向上汇总。
        left_count = dfs(node.left, next_max)
        right_count = dfs(node.right, next_max)
        return is_good + left_count + right_count

    return dfs(root, root.val)


if __name__ == "__main__":
    root = TreeNode(
        3,
        TreeNode(1, TreeNode(3)),
        TreeNode(4, TreeNode(1), TreeNode(5)),
    )
    print(count_good_nodes(root))

预期输出

text
4

这个实现没有共享可变状态,递归函数的输入和输出都很明确:参数 path_max 只向下传,返回的整数只向上传,因此每一层都可以独立检查。

用返回值组合父节点答案

很多树题甚至不需要向下参数。例如最大深度只需要左右子树各自返回高度,然后父节点返回 1 + max(left, right);判断平衡树则可以让子树返回高度,并用特殊值表示“不平衡”。

另一类题的最终答案不能只靠某一个子树返回值表示。例如二叉树直径常让递归返回“当前节点向下的最大高度”,同时用额外变量记录 left_height + right_height 的最大值。这里要分清两个职责:返回值服务父节点继续递归,额外汇总量服务最终答案。

用三个问题固定递归设计

遇到新的二叉树题,可以按下面顺序检查:

  1. 当前节点做判断时,是否依赖根到这里的历史信息?如果依赖,把它设计成参数向下传。
  2. 父节点组合答案时,需要从当前子树获得什么最小信息?把它设计成返回值。
  3. 最终答案是否等同于根节点返回值?如果不是,再增加一个明确的汇总位置,而不是把多个含义塞进同一个返回值。

只要参数、返回值和最终答案各自承担单一职责,递归终止条件通常也会自然清晰:空节点返回对应的“空子树结果”,非空节点先递归左右孩子,再组合并返回。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用递归返回值处理二叉树问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通