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 andsum = 22,5 / 4 8 / / 11 13 4 / \ / 7 2 5 1return
[ [5,4,11,2], [5,8,4,5] ]
算法思路：
跟[leetcode]Path Sum区别不大，dfs
代码如下：
1 public class Solution { 2 List<List<Integer>> res = new ArrayList<List<Integer>>(); 3 public List<List<Integer>> pathSum(TreeNode root, int sum) { 4 if(root == null) return res; 5 List<Integer> list = new ArrayList<Integer>(); 6 dfs(list, root, sum); 7 return res; 8 } 9 public void dfs(List<Integer> list,TreeNode root,int sum){ 10 if(root.left == null && root.right == null && root.val == sum){ 11 list.add(sum); 12 res.add(new ArrayList<Integer>(list)); 13 list.remove(list.size() - 1); 14 return; 15 } 16 if(root.left != null){ 17 list.add(root.val); 18 dfs(list, root.left, sum - root.val); 19 list.remove(list.size() - 1); 20 } 21 if(root.right!= null){ 22 list.add(root.val); 23 dfs(list, root.right, sum - root.val); 24 list.remove(list.size() - 1); 25 } 26 } 27 }
[leetcode]Path Sum II,布布扣,bubuko.com
原文：http://www.cnblogs.com/huntfor/p/3883544.html