algoadvance

Leetcode 113. Path Sum II

Problem Statement

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

Return:

[
   [5,4,11,2],
   [5,8,4,5]
]

Clarifying Questions

  1. What is the range of values in the tree?
    • The tree node values can be positive or negative integers.
  2. What is the range of the sum target?
    • The target can also be a positive or negative integer.
  3. Can the tree contain duplicate values?
    • Yes, the tree can have duplicate values.
  4. What is the size of the tree?
    • The size can vary but is generally assumed to fit within memory constraints.

Strategy

  1. Depth-First Search (DFS) Approach:
    • Traverse the tree using DFS to explore all paths starting from the root.
    • Maintain a current path list and a running sum of the current path.
    • When we reach a leaf node, check if the running sum equals the target sum and add the path to the result list if it does.
    • Use backtracking to ensure that after exploring one path, the state is reverted to explore other paths.

Code

import java.util.*;

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> currentPath = new ArrayList<>();
        findPaths(root, sum, currentPath, result);
        return result;
    }
    
    private void findPaths(TreeNode node, int sum, List<Integer> currentPath, List<List<Integer>> result) {
        if (node == null) {
            return;
        }
        
        currentPath.add(node.val);
        if (node.left == null && node.right == null && sum == node.val) {
            result.add(new ArrayList<>(currentPath));
        } else {
            findPaths(node.left, sum - node.val, currentPath, result);
            findPaths(node.right, sum - node.val, currentPath, result);
        }
        currentPath.remove(currentPath.size() - 1);
    }
    
    public static void main(String[] args) {
        // Example usage:
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.left = new TreeNode(5);
        root.right.right.right = new TreeNode(1);

        Solution sol = new Solution();
        System.out.println(sol.pathSum(root, 22));
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

Time Complexity

Hence, the overall space complexity could be O(2N), but we generally express it as O(N).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI