树形 DP 入门递归返回值要先想清楚一、树题难在状态方向树形 DP 常让人头疼不是因为代码一定很长而是因为状态方向容易乱。一个节点要从子节点拿什么信息返回给父节点什么答案是在子树里更新还是在根节点统一得到这些问题没想清楚递归就会写成一团。树形 DP 的第一步是定义递归返回值。二、先画信息流flowchart TD A[叶子节点] -- B[返回基础状态] B -- C[父节点合并子状态] C -- D[更新当前状态] D -- E[返回给更高层]树的天然结构适合后序遍历先处理子节点再合并到父节点。大多数树形 DP 都是在这个方向上工作。tree_dp_questions: return_meaning: required merge_children: required update_global_answer: optional base_case: required写代码前先回答这四个问题能少很多返工。三、例子二叉树最大路径和def max_path_sum(root): ans float(-inf) def dfs(node): nonlocal ans if not node: return 0 left max(dfs(node.left), 0) right max(dfs(node.right), 0) ans max(ans, node.val left right) return node.val max(left, right) dfs(root) return ans这里dfs(node)返回的是从当前节点向父节点延伸时能提供的最大单边路径和。为什么只能返回单边因为父节点如果继续连接路径不能在当前节点分叉后再往上走。但全局答案可以用左右两边同时更新node.val left right。返回值和答案更新含义不同这是树形 DP 最常见的关键点。四、不要把全局答案和返回值混在一起有些题返回值就是答案有些题需要全局变量。判断标准是父节点是否能直接使用这个值。如果某个值只在当前子树内部成立不能向父节点延伸就不要当返回值。def dfs(node): # return 给父节点的信息 # update 当前子树内部答案 pass写注释时明确这两层含义比写复杂变量名更有用。还要注意空节点的返回值。空节点返回 0、-inf、None取决于状态定义。不要因为模板里常写 0就所有题都写 0。最后树形 DP 的复杂度通常是 O(n)因为每个节点只处理一次。但如果每个节点合并子树时又扫描子树就会变成 O(n²)。合并成本也要算进去。多叉树题还要注意合并顺序。二叉树只有左右两个子节点状态合并容易写多叉树如果要选若干子树、统计前 k 个结果就可能变成背包式合并。此时每个节点的合并成本不一定是 O(度数)。tree_dp_merge_check: binary_tree: simple_merge multi_child_tree: consider_knapsack_merge rerooting: require_parent_contribution还有一类换根 DP需要同时考虑子树贡献和父方向贡献。普通后序返回值不够需要一次自底向上、一次自顶向下。看到“每个节点作为根的答案”时就要警惕这种模式。五、总结树形 DP 入门要先定义递归返回值、子状态合并方式、全局答案更新位置和空节点边界。递归返回值想清楚代码自然会短。没想清楚树再简单也会绕晕。