树形 DP

2026-06-02

一句话: DFS 一遍, 每个节点的答案 = 子树聚合 + 自己的贡献。本质是后序遍历 + 状态在节点上传递, 自底向上 return。

直觉 — DFS 后序 + 子树聚合

线性 DP 是”从左往右抄前面的状态”, 树形 DP 是”从叶子往根抄子树的状态”。换句话说, 树根本不需要新算法, 只是把”前一个状态”换成了”所有子节点的返回值”。

核心套路就一句话:

写一个 dfs(node), 后序递归两个孩子, 把孩子的返回值组合一下, 再 return 给父亲。

到节点 u 时, 我手上已经有 dfs(u.left) 和 dfs(u.right) 的结果。我要决定两件事:

  1. 当前节点贡献什么(更新全局答案 or 累加进自己的状态)
  2. 往上返回什么(父亲需要知道我子树的哪些信息才能继续算)

这两件事经常不一样。下面的动画用二叉树直径(LC 543)演示得最清楚: 节点要更新的”经过我的路径”是左链+右链, 但能往上返回的”延伸链”只能选一边 —— 因为路径不能在父亲那里分叉。

对照动画看后序顺序: 叶子 4 → 叶子 6 → 节点 5 → 节点 2 → 叶子 3 → 根 1。每访问一个节点, 蓝色 ↑ 是它返回给父亲的深度, 绿色是经过它的最长路径, 红色全局 ans 只在需要时被刷新。看完这段, 后面所有模板都是同一个骨架。

模板 — Python (dfs 返回 tuple)

骨架长这样, 几乎所有树形 DP 题都是它的变体:

1
2
3
4
5
6
7
8
9
10
11
12
13
def solve(root):
    ans = 0  # 如有全局答案就放外面
    def dfs(node):
        nonlocal ans
        if not node:
            return (0, 0, ...)            # 空节点的"零元"
        L = dfs(node.left)
        R = dfs(node.right)
        # 1. 用 L, R, node.val 更新全局 ans (如有)
        # 2. 算出当前节点要返回给父亲的状态 tuple
        return (state1, state2, ...)
    dfs(root)
    return ans

三件事必须想清楚再下笔:

  1. 空节点返回什么 —— 决定递归基。一般是 0 或 (0, 0), 但有些题(如最大路径和)是 -inf。
  2. 返回 tuple 里放几个状态 —— 单状态(深度)/ 两个状态(选 vs 不选)/ 更多(监控二叉树有 3 个)。
  3. 当前节点的贡献是局部还是全局 —— “经过我的”用来更新全局 ans, “延伸到我的”才能往上 return。两者不能混。

两类经典

子树聚合 — 二叉树直径 (LC 543)

直径 = 任意两节点之间的最长路径。关键区分: 路径可以在某个节点”拐弯”, 但拐弯的那一段不能再往上传。

1
2
3
4
5
6
7
8
9
10
11
def diameterOfBinaryTree(root):
    ans = 0
    def dfs(node):
        nonlocal ans
        if not node: return 0
        L = dfs(node.left)              # 左子树最长延伸链
        R = dfs(node.right)             # 右子树最长延伸链
        ans = max(ans, L + R)           # 经过我的路径(可拐弯, 更新全局)
        return max(L, R) + 1            # 给父亲的链(不能拐弯, 只能选一边)
    dfs(root)
    return ans

同款骨架直接套: LC 124 最大路径和 (空节点返回 0, 负贡献用 max(L, 0) 截断); LC 687 最长同值路径 (儿子值相同才能延伸)。

选/不选 — 打家劫舍 III (LC 337)

每个节点要么偷要么不偷, 偷了的话孩子就不能偷。返回 (偷我的最大值, 不偷我的最大值):

1
2
3
4
5
6
7
8
9
def rob(root):
    def dfs(node):
        if not node: return (0, 0)
        L = dfs(node.left)
        R = dfs(node.right)
        rob_me  = node.val + L[1] + R[1]    # 偷我 → 孩子必须不偷
        skip_me = max(L) + max(R)           # 不偷我 → 孩子选最大的
        return (rob_me, skip_me)
    return max(dfs(root))

注意 skip_me 取的是 max(L), 不是 L[1] —— 不偷自己时, 孩子可偷可不偷, 取大的那个。这条同款骨架的扩展:

  • LC 968 监控二叉树 — 每个节点 3 个状态(放摄像头 / 被覆盖 / 没覆盖), 返回 3 元组。
  • 树上独立集 / 最小点覆盖 —— 全是这套”选 vs 不选”。

进阶: 换根 DP (两次 DFS)

上面的模板都是”指定根之后的答案”。如果题目要”以每个节点为根时的答案”(如 LC 834 树中距离之和), 暴力对每个根跑一遍 DFS 就是 。

换根 DP 用两次 DFS:

  1. 第一次 DFS(后序): 钦定节点 0 为根, 算出 dp[0]。
  2. 第二次 DFS(前序): 从根往下传, 增量更新 dp[child] = dp[parent] + 偏移量。

关键是想出”父→子换根时, 答案的增量是什么”。一般是 的算式, 总复杂度 。

记忆法 / 易错点

一句话口诀: 后序递归两个孩子, 拼成 tuple 往上传, 全局答案在路上更。

3 个反复出错的点:

  1. 更新全局 vs return 给父亲是两件事 —— 直径 / 最大路径和题一旦把”拐弯路径”往上 return, 父亲那里就分叉, 全错。
  2. 空节点的零元 —— 求最大值且节点值可能为负时, 别想当然 return 0; 见 LC 124 用负贡献截断。
  3. 选/不选的 skip —— 不选当前节点时, 孩子能选可以不选, 取 max(L) 不是 L[1]。这个坑写打家劫舍 III 时几乎人人踩。

判题口诀:

  • 问”树上某种最优路径/直径” → 子树聚合, return 一条延伸链。
  • 问”选一些节点, 父子互斥” → 选/不选, return tuple。
  • 问”以每个节点为根时的答案” → 换根 DP, 两次 DFS。

思考题

1. 为什么树形 DP 要用后序遍历? 前序行不行?

后序意味着”先处理子节点, 再处理当前”。当前节点的答案依赖子节点的返回值, 所以必须后序。前序时子节点还没算, 没法组合。唯一例外是换根 DP 的第二次 DFS, 用父节点信息增量更新子节点, 那一趟用前序。

2. "经过当前节点的路径"和"延伸到当前节点的链"为什么不能混?

“经过我的路径” = 左链 + 我 + 右链, 是个倒 V, 可以是全局最优解。”延伸到我的链” = max(左, 右) + 我, 是直线。区别就在于路径可以在我这里拐弯, 但传给父亲的不能拐, 否则父亲那里就出现分叉, 父亲再往上就更乱了。

3. 换根 DP 为什么只要两次 DFS?

第一次 DFS 确定了”以 0 为根”的基准。换根从 parent 到 child, 只发生一个 的拓扑变化: child 的子树从”parent 下方”变成”parent 上方”。增量可算, 沿前序从上往下递推一遍即可, 共 。

LeetCode 练习

热身: 104 最大深度 · 543 直径 · 110 平衡二叉树 · 687 最长同值路径

进阶: 124 最大路径和 · 337 打家劫舍 III · 968 监控二叉树 · 834 树中距离之和 · 310 最小高度树