Path Problems (Path Sum · Maximum Path Sum · Diameter)

Path Sum Series

Path Sum I (LeetCode 112: Existence)

Existence of a root-to-leaf path summing to target:

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

Path Sum II (LeetCode 113: All Paths)

Collect all distinct root-to-leaf paths that satisfy the sum:

List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(root, targetSum, 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); // Backtrack
}

Path Sum III (LeetCode 437: Arbitrary Nodes)

Find the number of paths (can start/end anywhere as long as they go downward) that sum to target.
Technique: Prefix Sum + DFS.

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

int dfs(TreeNode node, long currSum, int target, Map<Long, Integer> prefixSumMap) {
    if (node == null) return 0;
    currSum += node.val;
    // Count previous prefixes that satisfy: currSum - previousSum = target
    int count = prefixSumMap.getOrDefault(currSum - target, 0);
    
    // Record current prefix sum
    prefixSumMap.merge(currSum, 1, Integer::sum);
    
    count += dfs(node.left, currSum, target, prefixSumMap);
    count += dfs(node.right, currSum, target, prefixSumMap);
    
    // Backtrack: Remove current prefix sum to avoid cross-path pollution
    prefixSumMap.merge(currSum, -1, Integer::sum);
    return count;
}

Binary Tree Maximum Path Sum (LeetCode 124)

Path can start and end at any node (peak-based approach).

Insight: DFS returns the "max gain" starting from the current node going down one branch, while updating the global maximum that treats the current node as the path's peak.

int maxGlobalSum = Integer.MIN_VALUE;

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

int gain(TreeNode node) {
    if (node == null) return 0;
    // Disregard paths with negative net gain
    int leftMax = Math.max(gain(node.left), 0);
    int rightMax = Math.max(gain(node.right), 0);
    
    // Update global maximum path considering the current node as the 'peak'
    maxGlobalSum = Math.max(maxGlobalSum, node.val + leftMax + rightMax);
    
    // Return maximum gain reachable via ONE child path to the parent
    return node.val + Math.max(leftMax, rightMax);
}

Diameter of Binary Tree (LeetCode 543)

Max diameter = Maximum value of leftDepth + rightDepth across all nodes:

int maxDiameter = 0;

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

int depth(TreeNode node) {
    if (node == null) return 0;
    int leftDepth = depth(node.left);
    int rightDepth = depth(node.right);
    
    // Diameter is number of edges, so sum of left and right child depths
    maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
    
    return 1 + Math.max(leftDepth, rightDepth);
}

Sum of Distances in Tree (LeetCode 834)

Rerooting DP: Calculate aggregate subtree sizes and distance sums from root 0 first (DFS 1), then derive results for other roots in O(1) per transition (DFS 2).

// Phase 1: Calculate metrics relative to root 0
void dfs(int u, int p) {
    subtreeSize[u] = 1;
    distSum[u] = 0;
    for (int v : graph.get(u)) {
        if (v == p) continue;
        dfs(v, u);
        subtreeSize[u] += subtreeSize[v];
        // Dist to u = Dist to v + subtree nodes (each gets +1 closer to parent)
        distSum[u] += distSum[v] + subtreeSize[v];
    }
}

// Phase 2: Reroot to pivot from u to child v
void reroot(int u, int p) {
    for (int v : graph.get(u)) {
        if (v == p) continue;
        // Total distance change when moving from u to v:
        // nodes in v's subtree get -1 closer, others (n - size[v]) get +1 further
        distSum[v] = distSum[u] - subtreeSize[v] + (totalNodes - subtreeSize[v]);
        reroot(v, u);
    }
}