首页 > 代码库 > [Leetcode] Path Sum II

[Leetcode] Path Sum II

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

 

 1 /** 2  * Definition for binary tree 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; } 8  * } 9  */10 public class Solution {11     public List<List<Integer>> pathSum(TreeNode root, int sum) {12          List<List<Integer>> result=new ArrayList<List<Integer>>();13         List<Integer> tmp=new ArrayList<Integer>();14         dfs(result,tmp,sum,root,0);15         return result;16     }17 18     private void dfs(List<List<Integer>> result, List<Integer> tmp, int sum, TreeNode root, int curSum) {19         // TODO Auto-generated method stub20         if(root==null)21             return;22         if(root.left==null&&root.right==null){23             if(curSum+root.val==sum){24                 tmp.add(root.val);25                 result.add(new ArrayList<Integer>(tmp));26                 tmp.remove(tmp.size()-1);27                 return;28             }29             return;30         }31         tmp.add(root.val);32         dfs(result,tmp,sum,root.left,curSum+root.val);33         dfs(result,tmp,sum,root.right,curSum+root.val);34         tmp.remove(tmp.size()-1);35     }36 }

 

[Leetcode] Path Sum II