Java recursive solution (backtracking)


  • 0
    2
    class Solution {
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            List<List<Integer>> lists = new ArrayList<List<Integer>>();
            ArrayList<Integer> l = new ArrayList<Integer>();
            backtrack(root, sum, l, lists);
            return lists;
        }
        
        public void backtrack(TreeNode root, int sum, ArrayList<Integer> l, List<List<Integer>> lists) {
            if(root==null) return;
            l.add(root.val);
            int size = l.size();
    
            if(root.left==null && root.right==null && sum-root.val==0) {
                lists.add(new ArrayList<Integer>(l));
                l.remove(size-1);
                return;
            }
            backtrack(root.left, sum-root.val, l, lists);
            backtrack(root.right, sum-root.val, l, lists);
            l.remove(size-1);
            return;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.