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

在树上汇总子树最优状态

在树上汇总子树最优状态

树形 DP 的核心不是“把数组 DP 搬到树上”,而是让每个节点只向父节点汇报少量足够的信息。以父子节点不能同时选择为例,只需维护“选当前节点”和“不选当前节点”两种子树最优值,再在后序遍历中合并孩子结果。

学习目标

  • 根据父子冲突约束为每个节点设计两类 DP 状态
  • 用后序遍历从孩子状态计算父节点状态
  • 实现树形 DP,并理解为什么根节点只需比较两种最终状态

把父节点真正需要的信息留下

假设每个树节点都有一个权值,要求选择若干节点,使任意父子节点不能同时被选,并让权值总和最大。对某个节点 u,父节点不需要知道它的子树中具体选了哪些节点,只需要知道两种结果:

  • take[u]:选择 u 时,u 的整棵子树能取得的最大权值
  • skip[u]:不选择 u 时,u 的整棵子树能取得的最大权值

这两个状态恰好对应父节点下一步决策所需的信息。如果父节点被选,那么孩子必须走 skip;如果父节点不选,每个孩子就可以在自己的 take 和 skip 中取更大值。

树形 DP 后序汇总选择与不选择状态

后序遍历就是计算顺序

设节点 u 的权值为 value[u],孩子集合为 children(u)。如果选择 u,所有孩子都不能选,因此:

take[u] = value[u] + sum(skip[v])

如果不选择 u,每个孩子可以独立选择更优状态,因此:

skip[u] = sum(max(take[v], skip[v]))

这里必须先得到所有孩子的状态,才能计算父节点,所以天然使用后序遍历:先递归处理子树,再处理当前节点。树形 DP 常见的“递归返回多个值”,本质就是把子树压缩成父节点真正需要的状态摘要。

用一个完整示例计算最优值

下面的二叉树对应权值结构:根节点 3 的左孩子为 2、右孩子为 3;左孩子还有右子节点 3,右孩子还有右子节点 1。父子不能同时选择。

python
from dataclasses import dataclass
from typing import Optional


@dataclass
class TreeNode:
    value: int
    left: Optional['TreeNode'] = None
    right: Optional['TreeNode'] = None


def best_subtree(node: Optional[TreeNode]) -> tuple[int, int]:
    if node is None:
        return 0, 0

    left_take, left_skip = best_subtree(node.left)
    right_take, right_skip = best_subtree(node.right)

    # 选择当前节点时,两个孩子都必须不选。
    take = node.value + left_skip + right_skip

    # 不选当前节点时,每个孩子都可以独立取更优状态。
    skip = max(left_take, left_skip) + max(right_take, right_skip)
    return take, skip


def max_weight(root: Optional[TreeNode]) -> int:
    take, skip = best_subtree(root)
    return max(take, skip)


if __name__ == '__main__':
    root = TreeNode(
        3,
        left=TreeNode(2, right=TreeNode(3)),
        right=TreeNode(3, right=TreeNode(1)),
    )
    print(max_weight(root))

预期输出

text
7

结果 7 可以由选择根节点 3、左下节点 3 和右下节点 1 得到。注意代码从未枚举“所有合法节点集合”,而是在每个节点处只保留两种最优摘要,因此避免了指数级组合搜索。

从二叉树推广到任意树

二叉树只是最容易写代码的形式。对任意多叉树,转移并没有改变:take[u] 仍然累加所有孩子的 skip,skip[u] 仍然累加每个孩子两种状态的较大值。只要树没有环,每条边在 DFS 中处理常数次,总时间复杂度为 O(n)。

状态本身只需每个节点两个值,若递归时即时返回而不额外保存整张表,额外空间主要来自递归栈,最坏为 O(h),其中 h 是树高;退化成链时可达到 O(n)。

判断树形 DP 状态是否够用

设计树形 DP 时,可以从“父节点为了做决策,究竟需要知道子树的哪些信息”出发,而不是先想数组下标。父子冲突问题只需要“选/不选”两态;如果约束变成“最多选一个孩子”“选择节点后距离两层内都不能选”等,状态就要增加能够描述这些边界条件的信息。

一个好的树形 DP 状态应当满足:孩子处理完后可以独立压缩成少量状态,父节点只依赖这些状态完成合并。只要这个条件成立,后序遍历就能把全树问题变成一次自底向上的局部汇总。

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

目录与阅读设置

阅读设置

17

记录一个想法

在树上汇总子树最优状态

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

登录哪都通