Neat recursive Java solution. 285ms.


  • 1

    It is DFS. Note that the val in root can be negative.

    public class Solution {
        static List<List<Integer>> ans;
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            ans = new LinkedList<List<Integer>>();
            helper (new LinkedList<Integer>(),root,sum);
            return ans;
        }
        
        public static void helper  (List<Integer> l , TreeNode root, int sum){
            if (root ==null) return;
            l.add(root.val);
            if (root.left==null && root.right==null && root.val==sum){
                ans.add(new LinkedList<Integer>(l));
            }else{
                helper (l,root.left,sum-root.val);
                helper (l,root.right,sum-root.val);
            }
            l.remove(l.size()-1);
        }
    }

Log in to reply
 

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