Given a binary tree and a sum, find all root-to-leaf paths where each path‘s sum equals the given sum.

              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);
		}
	}
}

Path Sum II