路径问题（路径总和 · 最大路径和 · 直径）

路径总和系列

路径总和 I（LeetCode 112，是否存在）

boolean hasPathSum(TreeNode root, int target) {
    if (root == null) return false;
    if (root.left == null && root.right == null) return root.val == target;
    return hasPathSum(root.left, target - root.val) || hasPathSum(root.right, target - root.val);
}

路径总和 II（LeetCode 113，所有路径）

List<List<Integer>> pathSum(TreeNode root, int target) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(root, target, new ArrayList<>(), result);
    return result;
}

void dfs(TreeNode node, int remain, List<Integer> path, List<List<Integer>> result) {
    if (node == null) return;
    path.add(node.val);
    if (node.left == null && node.right == null && remain == node.val) {
        result.add(new ArrayList<>(path));
    }
    dfs(node.left, remain - node.val, path, result);
    dfs(node.right, remain - node.val, path, result);
    path.remove(path.size() - 1);  // 回溯
}

路径总和 III（LeetCode 437，路径不需从根到叶）

前缀和 + DFS：

int pathSumIII(TreeNode root, int targetSum) {
    Map<Long, Integer> prefix = new HashMap<>();
    prefix.put(0L, 1);
    return dfs(root, 0, targetSum, prefix);
}

int dfs(TreeNode node, long curr, int target, Map<Long, Integer> prefix) {
    if (node == null) return 0;
    curr += node.val;
    int count = prefix.getOrDefault(curr - target, 0);
    prefix.merge(curr, 1, Integer::sum);
    count += dfs(node.left, curr, target, prefix) + dfs(node.right, curr, target, prefix);
    prefix.merge(curr, -1, Integer::sum);  // 回溯
    return count;
}

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

路径可以从任意节点到任意节点（不需过根）。

关键：DFS 返回"以当前节点为端点的最大路径"，同时更新全局最大值：

int maxPath = Integer.MIN_VALUE;

int maxPathSum(TreeNode root) {
    gain(root);
    return maxPath;
}

int gain(TreeNode node) {
    if (node == null) return 0;
    int left  = Math.max(gain(node.left), 0);   // 负收益不要
    int right = Math.max(gain(node.right), 0);
    // 过当前节点的最大路径
    maxPath = Math.max(maxPath, node.val + left + right);
    // 返回以当前节点为端点的最大增益（只能选一侧）
    return node.val + Math.max(left, right);
}

二叉树的直径（LeetCode 543）

直径 = 某节点的左右子树深度之和的最大值：

int diameter = 0;

int diameterOfBinaryTree(TreeNode root) {
    depth(root);
    return diameter;
}

int depth(TreeNode node) {
    if (node == null) return 0;
    int left = depth(node.left), right = depth(node.right);
    diameter = Math.max(diameter, left + right);
    return 1 + Math.max(left, right);
}

二叉树中所有节点的距离之和（LeetCode 834）

换根 DP：从根出发，先算一次 DFS 得各子树大小和深度和；再换根 DFS 推导其他根的答案。

// 步骤1（从根 0 的视角）
void dfs(int u, int parent) {
    size[u] = 1; dist[u] = 0;
    for (int v : graph.get(u)) {
        if (v == parent) continue;
        dfs(v, u);
        size[u] += size[v];
        dist[u] += dist[v] + size[v];  // 子树每个节点到 u 多走一步
    }
}

// 步骤2（换根）
void reroot(int u, int parent) {
    for (int v : graph.get(u)) {
        if (v == parent) continue;
        dist[v] = dist[u] - size[v] + (n - size[v]);
        reroot(v, u);
    }
}