113.Path Sum II

题目大意：题意见112题，这里就是找出所有路径，并且返回所有路径值。也就是要想办法把路径存起来。

法一：利用145的后序非递归遍历，因为在后序非递归遍历中，当要弹出某一个结点时，栈中所存的就是当前结点的所有父节点，也就是从根结点到当前结点的路径，所以很快想到用后序非递归。这里还有个要注意的点，就是在存入list的时候要新建对象，否则list存进去会是空值。代码如下（耗时6ms）：

 1     public List<List<Integer>> pathSum(TreeNode root, int sum) {
 2         List<List<Integer>> list = new ArrayList<List<Integer>>();
 3         if(root == null) {
 4             return list;
 5         }
 6         Stack<TreeNode> stack = new Stack<TreeNode>();
 7         stack.push(root);
 8         TreeNode pre = null, cur = root.left;
 9         List<Integer> listIn = new ArrayList<Integer>();
10         listIn.add(root.val);
11         int cnt = root.val;
12         while(!stack.isEmpty()) {
13             while(cur != null) {
14                 stack.push(cur);
15                 listIn.add(cur.val);
16                 cnt += cur.val;
17                 cur = cur.left;
18             }//System.out.println(listIn);
19             cur = stack.peek();
20             if(cur.left == null && cur.right == null && cnt == sum) {
21                 //每次加入的时候新new一个对象，这个很重要
22                 list.add(new ArrayList<Integer>(listIn));
23             }
24             if(cur.right != null && pre != cur.right) {
25                 cur = cur.right;
26             }
27             else {
28                 cnt -= cur.val;
29                 listIn.remove(listIn.size() - 1);
30                 stack.pop();
31                 pre = cur;
32                 cur = null;
33             }
34         }
35         return list;
36     }

View Code

法二：利用112的dfs办法。只是回溯的时候多了list.remove的操作。代码如下（耗时3ms）：

 1     public List<List<Integer>> pathSum(TreeNode root, int sum) {
 2         List<List<Integer>> list = new ArrayList<List<Integer>>();
 3         List<Integer> listIn = new ArrayList<Integer>();
 4         if(root == null) {
 5             return list;
 6         }
 7         int cnt = 0;
 8         list = dfs(root, list, listIn, sum, cnt);
 9         return list;
10     }
11     public static List<List<Integer>> dfs(TreeNode root, List<List<Integer>> list, List<Integer> listIn, int sum, int cnt) {
12         listIn.add(root.val);
13         cnt += root.val;
14         if(root.left == null && root.right == null) {
15             if(cnt == sum) {
16                 list.add(new ArrayList<Integer>(listIn));
17             }
18             return list;
19         }
20         if(root.left != null) {
21             list = dfs(root.left, list, listIn, sum, cnt);
22             //需要回溯remove，因为list是集合，在任何一处的修改都会修改原值，所以需要回溯后删除
23             listIn.remove(listIn.size() - 1);
24             //不需要回溯减，因为cnt是基本类型，传进去后的修改，并不会对原值有任何改变
25             //所以return后也不需要回溯，不然就多减了
26         //    cnt -= root.val;
27         }
28         if(root.right != null) {
29             list = dfs(root.right, list, listIn, sum, cnt);
30             listIn.remove(listIn.size() - 1);
31         //    cnt -= root.val;
32         }
33         return list;
34     }

View Code