Given a binary tree and a sum, find all root-to-leaf paths where each paths sum equals the given sum.For example:Given the below binary tree andsum =
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]
]
要写出路径和满足要求的所有路径 典型的回溯法递归求解 代码如下：
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res=new ArrayList<List<Integer>>(0);
List<Integer> tmp=new ArrayList<Integer>();
pathsearch(res, tmp, sum, 0, root);
return res;
}
public void pathsearch(List<List<Integer>> res,List<Integer> tmp,int sum,int cur,TreeNode root){
if(root==null)return;
List<Integer> ntmp=new ArrayList<Integer>();
ntmp.addAll(tmp);
ntmp.add(root.val);
if(root.left==null&&root.right==null){
if(sum==cur+root.val){
res.add(ntmp);
}
return;
}
if(root.left!=null){
pathsearch(res, ntmp, sum, cur+root.val, root.left);
}
if(root.right!=null){
pathsearch(res, ntmp, sum, cur+root.val, root.right);
}
}
}
，
