2.13 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.

For 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] ]

Method

deapth first search

Time and Space Complexity

o(n)

Code

public class Solution {

public List<List<Integer>> pathSum(TreeNode root, int sum) {
       List<List<Integer>> ans = new ArrayList<List<Integer>>();
       if (root == null){
           return ans;
       }
       dfs(root, sum, ans, new ArrayList<Integer>());
       return ans;
}

public void dfs(TreeNode root, int target, List<List<Integer>> ans, List<Integer> list){
       if (root == null){
           return;
       }
       list.add(root.val);
       if (root.left == null && root.right == null){
           if (root.val == target){
               ans.add(new ArrayList<Integer>(list));
           }
       }
       dfs(root.left, target - root.val, ans, list);
       dfs(root.right, target - root.val, ans, list);
       list.remove(list.size() - 1);

}

}