|
| 1 | +/* |
| 2 | + Author: King, higuige@gmail.com |
| 3 | + Date: Oct 7, 2014 |
| 4 | + Problem: Path Sum 2 |
| 5 | + Difficulty: easy |
| 6 | + Source: https://oj.leetcode.com/problems/path-sum-ii/ |
| 7 | + Notes: |
| 8 | + Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. |
| 9 | +
|
| 10 | + For example: |
| 11 | + Given the below binary tree and sum = 22, |
| 12 | + 5 |
| 13 | + / \ |
| 14 | + 4 8 |
| 15 | + / / \ |
| 16 | + 11 13 4 |
| 17 | + / \ / \ |
| 18 | + 7 2 5 1 |
| 19 | + return |
| 20 | + [ |
| 21 | + [5,4,11,2], |
| 22 | + [5,8,4,5] |
| 23 | + ] |
| 24 | +
|
| 25 | + Solution: DFS. |
| 26 | + */ |
| 27 | + |
| 28 | +/** |
| 29 | + * Definition for binary tree |
| 30 | + * public class TreeNode { |
| 31 | + * int val; |
| 32 | + * TreeNode left; |
| 33 | + * TreeNode right; |
| 34 | + * TreeNode(int x) { val = x; } |
| 35 | + * } |
| 36 | + */ |
| 37 | +publicclassSolution { |
| 38 | +publicList<List<Integer>>pathSum(TreeNoderoot,intsum) { |
| 39 | +List<List<Integer>>res =newArrayList<List<Integer>>(); |
| 40 | +ArrayList<Integer>path =newArrayList<Integer>(); |
| 41 | +pathSumRe(root,sum,res,path); |
| 42 | +returnres; |
| 43 | + } |
| 44 | +publicvoidpathSumRe(TreeNoderoot,intsum,List<List<Integer>>res,ArrayList<Integer>path) |
| 45 | + { |
| 46 | +if (root ==null)return; |
| 47 | +path.add(root.val); |
| 48 | +if (root.left ==null &&root.right ==null &&root.val ==sum){ |
| 49 | +ArrayList<Integer>tmp =newArrayList<Integer>(path); |
| 50 | +res.add(tmp); |
| 51 | + } |
| 52 | +pathSumRe(root.left,sum -root.val,res,path); |
| 53 | +pathSumRe(root.right,sum -root.val,res,path); |
| 54 | +path.remove(path.size()-1); |
| 55 | + } |
| 56 | +} |
| 57 | + |
