树形 DP (Tree DP)

[!abstract] 核心思想 在树结构上进行 DP，通常用 DFS 后序遍历，自底向上计算子树的状态。

---

基本模板

function dfs(node: TreeNode): [selected, notSelected] {
  // 后序遍历，先处理子树
  let selected = node.val || 0;
  let notSelected = 0;

  for (const child of node.children) {
    const [childSelected, childNotSelected] = dfs(child);
    selected += childNotSelected; // 选了当前节点，不能选子节点
    notSelected += Math.max(childSelected, childNotSelected); // 不选当前节点，选不选子节点都行
  }

  return [selected, notSelected];
}

---

1. 打家劫舍 III

问题

• 二叉树版抢房子，不能抢连续两层

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number) { this.val = val ?? 0; }
}

function rob(root: TreeNode | null): number {
  const [selected, notSelected] = dfs(root);
  return Math.max(selected, notSelected);
}

function dfs(node: TreeNode | null): [number, number] {
  // [选这个节点, 不选这个节点]
  if (!node) return [0, 0];

  const [leftSelected, leftNotSelected] = dfs(node.left);
  const [rightSelected, rightNotSelected] = dfs(node.right);

  // 选当前节点：子节点不能选
  const select = node.val + leftNotSelected + rightNotSelected;

  // 不选当前节点：子节点可选可不选
  const notSelect = Math.max(leftSelected, leftNotSelected) +
                    Math.max(rightSelected, rightNotSelected);

  return [select, notSelect];
}

状态转移

---

2. 二叉树最大路径和

问题

• 任意节点到任意节点的路径，和最大

function maxPathSum(root: TreeNode | null): number {
  let maxSum = -Infinity;

  function dfs(node: TreeNode | null): number {
    if (!node) return 0;

    const leftGain = Math.max(dfs(node.left), 0);
    const rightGain = Math.max(dfs(node.right), 0);

    // 以当前节点为拐点的路径
    const pathThroughNode = node.val + leftGain + rightGain;
    maxSum = Math.max(maxSum, pathThroughNode);

    // 返回给父节点，只能选一条边
    return node.val + Math.max(leftGain, rightGain);
  }

  dfs(root);
  return maxSum;
}

图解

        10
       /  \
      9    20
          /  \
         15   7

最大路径: 9 -> 10 -> 20 -> 15 = 54

---

3. 树的直径

问题

• 树中任意两节点间最长距离

let diameter = 0;

function diameterOfBinaryTree(root: TreeNode | null): number {
  diameter = 0;
  dfs(root);
  return diameter;
}

function dfs(node: TreeNode | null): number {
  if (!node) return 0;

  const left = dfs(node.left);
  const right = dfs(node.right);

  // 更新直径：左深度 + 右深度
  diameter = Math.max(diameter, left + right);

  // 返回给父节点的最大深度
  return Math.max(left, right) + 1;
}

---

4. 树的独立集

问题

• 选择尽量多的节点，任意两个选中的节点不相邻

function maxIndependentSet(root: TreeNode | null): number {
  const [selected, notSelected] = dfs(root);
  return Math.max(selected, notSelected);
}

function dfs(node: TreeNode | null): [number, number] {
  // [选自己, 不选自己]
  if (!node) return [0, 0];

  let select = node.val;
  let notSelect = 0;

  for (const child of node.children || []) {
    const [cSelected, cNotSelected] = dfs(child);
    select += cNotSelected;      // 选了自己，子节点不能选
    notSelect += Math.max(cSelected, cNotSelected); // 不选自己，子节点随意
  }

  return [select, notSelect];
}

---

5. 重心/最大子树

问题

• 删除一个节点后，最大的连通块最小

function findMinHeightRoots(root: TreeNode | null): number[] {
  const n = 10; // 节点数（假设）
  const heights = Array(n).fill(0);
  const counts = Array(n).fill(0);

  function dfs(node: TreeNode | null, parent: number) {
    if (!node) return;
    let size = 1;
    let maxSubtree = 0;

    for (const child of node.children) {
      if (child !== parent) {
        dfs(child, node.val);
        size += counts[child.val];
        maxSubtree = Math.max(maxSubtree, counts[child.val]);
      }
    }

    counts[node.val] = size;
    heights[node.val] = Math.max(maxSubtree, n - size);
  }

  dfs(root, -1);

  const minHeight = Math.min(...heights);
  return heights.map((h, i) => h === minHeight ? i : -1).filter(i => i >= 0);
}

---

6. 树的 DP 通用模板

// 多叉树的通用后序遍历 DP
function treeDP(root: TreeNode): Result {
  // 1. 初始化返回值
  let result = init();

  // 2. 遍历所有子节点
  for (const child of root.children) {
    const childResult = treeDP(child);
    // 3. 合并子节点结果到当前节点
    result = merge(result, childResult);
  }

  // 4. 用子节点结果更新当前节点
  updateCurrentNode(result);

  // 5. 返回结果
  return result;
}

---

常见题型

题型	状态	转移
抢房子	[选, 不选]	选了自己↔子节点不能选
最大路径和	返回深度	val + max(左，右)
树的直径	返回深度	max(直径, 左+右)
独立集	[选, 不选]	选了自己→子节点不选
覆盖问题	[选, 覆盖, 不覆盖]	三状态转移

---

参见: **DP算法索引** | **状态压缩DP**