Path SUm I, II, II

XXX. Path Sum Problems

Recursion

Depth-First Search

Hash Map

Problem Statement:

Path Sum I: Given a binary tree and a target sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given target sum.

Path Sum II: Find all root-to-leaf paths where each path's sum equals the given target sum.

Path Sum III: Count the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards.

Algorithm:

Path Sum I:

1. Base case: If the root is null, return false.
2. If the current node is a leaf node, check if the remaining target sum equals the node's value.
3. Recursively check the left and right subtrees, reducing the target sum by the current node's value.

Path Sum II:

1. Use a depth-first search (DFS) to explore all root-to-leaf paths.
2. Maintain a temporary list to store the current path.
3. If a leaf node is reached and the remaining sum is zero, add the current path to the result list.
4. Backtrack by removing the last node from the path list.

Path Sum III:

1. Use a hash map to store cumulative sums and their frequencies.
2. At each node, calculate the current cumulative sum and check if there exists a prefix sum that matches the target.
3. Update the hash map with the current cumulative sum and recursively process the left and right subtrees.
4. Backtrack by decrementing the frequency of the current cumulative sum in the hash map.

Complexity:

Path Sum I:
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(h), where h is the height of the tree (due to recursion stack).

Path Sum II:
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(h) for the recursion stack and O(h) for the temporary path list.

Path Sum III:
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(n) for the hash map.

Java Implementation:

// Path Sum I
public boolean hasPathSumI(TreeNode root, int targetSum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) 
        return targetSum == root.val;
    return hasPathSum(root.left, targetSum - root.val) || 
           hasPathSum(root.right, targetSum - root.val);
}

// Path Sum II
public List> pathSumII(TreeNode root, int sum) {
    List> result = new ArrayList<>();
    List tempList = new ArrayList<>();
    dfs(root, result, tempList, sum);
    return result;
}

public void dfs(TreeNode node, List> result, List tempList, int sum) {
    if (node == null) return;
    tempList.add(node.val);
    if (node.left == null && node.right == null && sum - node.val == 0) 
        result.add(new ArrayList<>(tempList));
    dfs(node.left, result, tempList, sum - node.val);
    dfs(node.right, result, tempList, sum - node.val);
    tempList.remove(tempList.size() - 1);
}

// Path Sum III
public int pathSumIII(TreeNode root, int sum) {
    HashMap preSum = new HashMap<>();
    preSum.put(0, 1);
    return helper(root, 0, sum, preSum);
}

public int helper(TreeNode root, int currSum, int target, HashMap preSum) {
    if (root == null) return 0;
    currSum += root.val;
    int res = preSum.getOrDefault(currSum - target, 0);
    preSum.put(currSum, preSum.getOrDefault(currSum, 0) + 1);
    res += helper(root.left, currSum, target, preSum) + 
           helper(root.right, currSum, target, preSum);
    preSum.put(currSum, preSum.get(currSum) - 1);
    return res;
}
                

Python Implementation:

def hasPathSumI(root, targetSum):
    if not root:
        return False
    if not root.left and not root.right:
        return targetSum == root.val
    return hasPathSumI(root.left, targetSum - root.val) or \
           hasPathSumI(root.right, targetSum - root.val)

def pathSumII(root, target):
    result = []
    def dfs(node, path, target):
        if not node:
            return
        path.append(node.val)
        if not node.left and not node.right and target == node.val:
            result.append(list(path))
        dfs(node.left, path, target - node.val)
        dfs(node.right, path, target - node.val)
        path.pop()
    dfs(root, [], target)
    return result

def pathSumIII(root, target):
    preSum = {0: 1}
    def helper(node, currSum):
        if not node:
            return 0
        currSum += node.val
        res = preSum.get(currSum - target, 0)
        preSum[currSum] = preSum.get(currSum, 0) + 1
        res += helper(node.left, currSum) + helper(node.right, currSum)
        preSum[currSum] -= 1
        return res
    return helper(root, 0)
                

C++ Implementation:

bool hasPathSumI(TreeNode* root, int targetSum) {
    if (!root) return false;
    if (!root->left && !root->right) return targetSum == root->val;
    return hasPathSumI(root->left, targetSum - root->val) || 
           hasPathSumI(root->right, targetSum - root->val);
}

vector> pathSumII(TreeNode* root, int target) {
    vector> result;
    vector path;
    function dfs = [&](TreeNode* node, int target) {
        if (!node) return;
        path.push_back(node->val);
        if (!node->left && !node->right && target == node->val) 
            result.push_back(path);
        dfs(node->left, target - node->val);
        dfs(node->right, target - node->val);
        path.pop_back();
    };
    dfs(root, target);
    return result;
}

int pathSumIII(TreeNode* root, int target) {
    unordered_map preSum = {{0, 1}};
    function helper = [&](TreeNode* node, int currSum) {
        if (!node) return 0;
        currSum += node->val;
        int res = preSum[currSum - target];
        preSum[currSum]++;
        res += helper(node->left, currSum) + helper(node->right, currSum);
        preSum[currSum]--;
        return res;
    };
    return helper(root, 0);
}