Path Sum Ii - Leetcode Solution

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

Example: Input: Given the below binary tree and sum = 22, 5 /
4 8 / /
11 13 4 / \ /
7 2 5 1 Output: [ [5,4,11,2], [5,8,4,5] ]

Solution: We will solve this problem using recursion. We will create a helper method that takes the current node, the current path, the target sum, and the result list as parameters. We will traverse the tree in a depth-first manner and check if the current node is a leaf node, i.e., it has no children. If yes, then we check if the current path's sum is equal to the target sum. If yes, then we add the current path to the result list.

If the current node is not a leaf node, then we recursively call the helper method with the left child and the right child. We pass the current path updated with the current node's value to both the recursive calls.

Here is the Java code:

public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> result = new ArrayList<>(); List<Integer> path = new ArrayList<>(); pathSumHelper(root, path, sum, result); return result; }

private void pathSumHelper(TreeNode node, List<Integer> path, int sum, List<List<Integer>> result) { if (node == null) { return; }

path.add(node.val);

if (node.left == null && node.right == null && node.val == sum) {
    result.add(new ArrayList<>(path));
} else {
    pathSumHelper(node.left, path, sum - node.val, result);
    pathSumHelper(node.right, path, sum - node.val, result);
}

path.remove(path.size() - 1);

}

We create a List object to store the final result and initialize an empty ArrayList to store the current path. We then call the helper method with the root node, the empty path, the target sum, and the result list.

In the helper method, we first check if the current node is null. If yes, then we return. If the current node is not null, we add its value to the path.

We then check if the current node is a leaf node or not. If it is a leaf node, we check if the current path's sum is equal to the target sum. If yes, then we append the current path to the result list. If it is not a leaf node, we recursively call the helper method with the left and right child nodes. We pass the updated path and subtract the current node's value from the target sum.

Finally, we remove the last element from the path before exiting the function, as we need to remove the last node before going to the previous level in the recursion.

The time complexity of this solution is O(N^2) as in the worst-case scenario, we visit all nodes in the binary tree, and for each node, we create a new list to store the path. The space complexity is also O(N^2) as in the worst-case scenario, we store all paths from the root node to the leaf nodes in our result list.

1