树形动态规划：为什么一棵树的答案要从叶子开始算

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
}

class Solution {
    private int maxDiameter = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return maxDiameter;
    }
    
    // 返回以 node 为根的子树的高度（最大深度 - 1，即边数）
    private int height(TreeNode node) {
        if (node == null) return -1;  // 空节点高度为 -1，这样叶子节点高度为 0
        
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);
        
        // 更新全局答案：经过当前节点的最长路径
        int diameter = leftHeight + rightHeight + 2;
        maxDiameter = Math.max(maxDiameter, diameter);
        
        // 返回子树高度，供父节点使用
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

class Solution {
    private int maxSum = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }
    
    // 返回以 node 为起点，向下的最大路径和（只能选一边）
    private int maxGain(TreeNode node) {
        if (node == null) return 0;
        
        // 递归计算左右子树的最大贡献
        // 如果贡献为负，不如不选（选择空路径，贡献为0）
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);
        
        // 经过当前节点的最大路径和
        int pathSum = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, pathSum);
        
        // 返回当前节点能向父节点贡献的最大值（只能选一边）
        return node.val + Math.max(leftGain, rightGain);
    }
}

class Solution {
    public int rob(TreeNode root) {
        int[] result = dfs(root);
        return Math.max(result[0], result[1]);
    }
    
    // 返回数组 [选中当前节点的最大收益, 不选中当前节点的最大收益]
    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        
        // 选中当前节点：子节点必须不选中
        int selected = node.val + left[1] + right[1];
        
        // 不选中当前节点：子节点选或不选均可，取最大
        int notSelected = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        
        return new int[]{selected, notSelected};
    }
}

class Solution {
    private int cameras = 0;
    private final int COVERED = 0;      // 被监控，无摄像头
    private final int HAS_CAMERA = 1;   // 有摄像头
    private final int NOT_COVERED = 2;  // 未被监控
    
    public int minCameraCover(TreeNode root) {
        if (dfs(root) == NOT_COVERED) {
            cameras++;  // 根节点未被监控，需要放置摄像头
        }
        return cameras;
    }
    
    private int dfs(TreeNode node) {
        if (node == null) return COVERED;  // 空节点视为已覆盖
        
        int left = dfs(node.left);
        int right = dfs(node.right);
        
        // 如果任一子节点未被监控，当前节点必须放摄像头
        if (left == NOT_COVERED || right == NOT_COVERED) {
            cameras++;
            return HAS_CAMERA;
        }
        
        // 如果任一子节点有摄像头，当前节点被覆盖
        if (left == HAS_CAMERA || right == HAS_CAMERA) {
            return COVERED;
        }
        
        // 两个子节点都被监控但没有摄像头，当前节点未被覆盖
        return NOT_COVERED;
    }
}

class Solution {
    private int maxLength = 0;
    
    public int longestUnivaluePath(TreeNode root) {
        arrowLength(root);
        return maxLength;
    }
    
    // 返回从 node 出发，向下的同值路径最大长度（只能走一边）
    private int arrowLength(TreeNode node) {
        if (node == null) return 0;
        
        int leftArrow = arrowLength(node.left);
        int rightArrow = arrowLength(node.right);
        
        // 计算向左的同值路径长度
        int leftPath = 0;
        if (node.left != null && node.left.val == node.val) {
            leftPath = leftArrow + 1;
        }
        
        // 计算向右的同值路径长度
        int rightPath = 0;
        if (node.right != null && node.right.val == node.val) {
            rightPath = rightArrow + 1;
        }
        
        // 更新全局答案：穿过当前节点的同值路径
        maxLength = Math.max(maxLength, leftPath + rightPath);
        
        // 返回单边最大长度
        return Math.max(leftPath, rightPath);
    }
}

class Solution {
    private List<List<Integer>> graph;
    private int[] count;
    private int[] distSum;
    private int n;
    
    public int[] sumOfDistancesInTree(int n, int[][] edges) {
        this.n = n;
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        
        count = new int[n];
        distSum = new int[n];
        
        // 第一次 DFS：计算 count[] 和 distSum[0]
        dfs1(0, -1);
        // 第二次 DFS：推导其他节点的 distSum
        dfs2(0, -1);
        
        return distSum;
    }
    
    private void dfs1(int node, int parent) {
        count[node] = 1;
        for (int child : graph.get(node)) {
            if (child == parent) continue;
            dfs1(child, node);
            count[node] += count[child];
            distSum[node] += distSum[child] + count[child];
        }
    }
    
    private void dfs2(int node, int parent) {
        for (int child : graph.get(node)) {
            if (child == parent) continue;
            distSum[child] = distSum[node] - count[child] + (n - count[child]);
            dfs2(child, node);
        }
    }
}