113. Path Sum II

Description

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

Note: A leaf is a node with no children.

Constraints

Approach

Examples

Input:

tree=[5,4,8,11,null,13,4,7,2,null,null,5,1]

sum=22

Output:

[

[5, 4, 11, 2],

[5, 8, 4, 5]

]

Explanation:

Solutions

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    
    TreeNode(int val) { this.val = val; }
    
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Time complexity : O(N^2) where N are the number of nodes in a tree.
 * Space complexity : O(N)
 */

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> resultList = new ArrayList();
        if(root == null) return resultList;
        helper(resultList, new LinkedList<Integer>(), root, sum);
        return resultList;
    }
    
    private void helper(List<List<Integer>> resultList,
                        LinkedList<Integer> currList,
                        TreeNode node,
                        int sum) {
        if(node == null) return;
        
        currList.add(node.val);
        
        if(sum == node.val && node.left == null && node.right == null) {
            resultList.add(new ArrayList(currList));
        } else {
            helper(resultList, currList, node.left, sum-node.val);
            helper(resultList, currList, node.right, sum-node.val);
        }
        
        currList.removeLast();
    }
}