Wednesday, March 18, 2015

113. Path Sum II Leetcode Java

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]
]
Solution:
Recursive DFS
Base case/ terminating case:
current node is leaf node: if sum==target, add the sum to path and add the path to result list otherwise do nothing.
Recursion steps:
Try current node: if current.left is not null, recursively check its left subtree, when backtrack to current node, recursively check its right subtree, if cur.right is not null as well. 
 public List<List<Integer>> pathSum(TreeNode root, int sum) {  
     List<List<Integer>> res=new ArrayList<List<Integer>>();  
     List<Integer> paths=new ArrayList<Integer>();  
     helper(res,paths,root,sum);  
     return res;  
   }  
   public void helper(List<List<Integer>> res, List<Integer> paths,TreeNode root, int sum){  
     if(root==null) return;  
     if(root.left==null && root.right==null && sum==root.val){  
       List<Integer> temp=new ArrayList<Integer>(paths);  
       temp.add(sum);  
       res.add(temp);  
       return;  
     }  
     if(root.left!=null){  
       paths.add(root.val);  
       helper(res,paths,root.left, sum-root.val);  
       paths.remove(paths.size()-1);  
     }  
     if(root.right!=null){  
       paths.add(root.val);  
       helper(res,paths,root.right,sum-root.val);  
       paths.remove(paths.size()-1);  
     }  
   }  

No comments:

Post a Comment