树形 DP：打家劫舍III与树上问题

打家劫舍 III（LeetCode 337）

二叉树版本：不能选相邻（父子）节点，求最大价值：

后序遍历（DFS + DP），对每个节点返回 [不选该节点的最大值, 选该节点的最大值]：

public int rob(TreeNode root) {
    int[] res = dfs(root);
    return Math.max(res[0], res[1]);
}

// 返回 int[]{不选root的最大值, 选root的最大值}
private int[] dfs(TreeNode node) {
    if (node == null) return new int[]{0, 0};
    int[] left  = dfs(node.left);
    int[] right = dfs(node.right);
    // 不选 node：左右子树各自取最大
    int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    // 选 node：左右子节点都不能选
    int rob = node.val + left[0] + right[0];
    return new int[]{notRob, rob};
}

监控二叉树（LeetCode 968）

给二叉树最少安装多少摄像头，使每个节点被覆盖（摄像头覆盖自身及父子节点）：

贪心 DFS，返回 3 种状态：

• 0：该节点无摄像头，且未被覆盖（需要父节点安装摄像头）
• 1：该节点无摄像头，但已被子节点摄像头覆盖
• 2：该节点有摄像头

int count = 0;
public int minCameraCover(TreeNode root) {
    // 根节点若未被覆盖，强制安装
    return dfs(root) == 0 ? count + 1 : count;
}

private int dfs(TreeNode node) {
    if (node == null) return 1; // 空节点视为已覆盖
    int left = dfs(node.left), right = dfs(node.right);
    // 只要有子节点未被覆盖，必须在本节点安装摄像头
    if (left == 0 || right == 0) { count++; return 2; }
    // 有子节点安装了摄像头（状态2），本节点已被覆盖
    if (left == 2 || right == 2) return 1;
    // 两个子节点都是状态1（已覆盖但无摄像头），本节点未被覆盖
    return 0;
}

二叉树中的最大路径和（LeetCode 124）

路径可以从任意节点出发、到任意节点终止（不要求经过根）：

int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
    dfs(root);
    return maxSum;
}

// 返回以 node 为端点向下延伸的最大路径值（贡献值）
private int dfs(TreeNode node) {
    if (node == null) return 0;
    int left  = Math.max(dfs(node.left),  0); // 负数不取
    int right = Math.max(dfs(node.right), 0);
    // 更新全局最大（可能不过 node）
    maxSum = Math.max(maxSum, node.val + left + right);
    // 返回单边最大贡献
    return node.val + Math.max(left, right);
}

总结