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 a binary tree node. 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>> all = new ArrayList<List<Integer>>(); 13 helper(root, new ArrayList<Integer>(), all, 0, sum); 14 return all; 15 } 16 17 private void helper(TreeNode root, List<Integer> list, List<List<Integer>> all, int currSum, int sum) { 18 // exit condition 19 if (root == null) return; 20 21 list.add(root.val); 22 currSum += root.val; 23 24 if (currSum == sum && root.left == null && root.right == null) { 25 all.add(new ArrayList<Integer>(list)); 26 } 27 28 helper(root.left, list, all, currSum, sum); 29 helper(root.right, list, all, currSum, sum); 30 list.remove(list.size() - 1); 31 } 32 }
Path Sum III
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ 5 -3
/ \ 3 2 11
/ \ 3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
1 /** 2 * Definition for a binary tree node. 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 int pathSum(TreeNode root, int sum) { 12 int[] arr = new int[1]; 13 preOrder(root, sum, arr); 14 return arr[0]; 15 } 16 17 public void preOrder(TreeNode root, int sum, int[] count) { 18 if (root == null) return; 19 printSums(root, sum, 0, count); 20 preOrder(root.left, sum, count); 21 preOrder(root.right, sum, count); 22 } 23 24 public void printSums(TreeNode n, int sum, int currentSum, int[] count) { 25 if (n == null) return; 26 int newSum = currentSum + n.val; 27 if (newSum == sum) { 28 count[0]++; 29 } 30 printSums(n.left, sum, newSum, count); 31 printSums(n.right, sum, newSum, count); 32 } 33 }
原文：http://www.cnblogs.com/beiyeqingteng/p/6238634.html