转载

[原]LeetCode 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

[    [5,4,11,2],    [5,8,4,5] ]

思路分析：这题是LeetCode Path Sum问题的变形题目，要求保存所有满足等于某个和的路径，仍然可以用DFS搜索解决，边DFS遍历树边保存下当前经过路径上的节点。和LeetCode Path Sum相比，有一个tricky的地方就是，回溯之后我们多了一句curPath.remove(curPath.size() - 1); 这是恢复“现场”，也就是把curPath恢复到递归调用之前的状态。那么问题来了，为什么我们只对curPath恢复现场，而不对curSum恢复现场呢（为何没有curSum-=curPath.get(curPath.size() - 1)）？这就涉及到对java参数传递何时传值何时传引用（也就是地址）的理解了，简而言之，基础数据类型（int，char，……）传值，对象类型（Object，数组，容器……）传引用。所以，递归调用里面如果修改了curPath这个容器对象的内容，当回溯的时候我们需要恢复现场，而对于curSum这个int类型我们没必要这么操作，因为递归调用根本没有修改它的值，我们递归调用时对int传入的是一份拷贝，而对ArrayList传入的是引用或者地址。传引用还是传拷贝是很细致的问题，但是在递归实现的时候这些细节必须处理好，不然容易引入bug。时间复杂度O（n），空间复杂度O（klogn），k为合法路径条数。

AC Code

/**  * Definition for binary tree  * public class TreeNode {  *  int val;  *  TreeNode left;  *  TreeNode right;  *  TreeNode(int x) { val = x; }  * }  */ public class Solution {  public List<List<Integer>> pathSum(TreeNode root, int sum) {   List<List<Integer>> pathRes = new ArrayList<List<Integer>>();   List<Integer> curPath = new ArrayList<Integer>();   helper(root, sum, 0, pathRes, curPath);   return pathRes;  }  public void helper(TreeNode root, int target, int curSum, List<List<Integer>> pathRes, List<Integer> curPath){   if(root == null) return;   curSum += root.val;   curPath.add(root.val);   if(root.left == null && root.right ==  null && curSum == target) {    pathRes.add(new ArrayList(curPath));    return;   }   if(root.left != null){    helper(root.left, target, curSum, pathRes, curPath);    curPath.remove(curPath.size() - 1);   }   if(root.right != null){    helper(root.right, target, curSum, pathRes, curPath);    curPath.remove(curPath.size() - 1);   }  } }

正文到此结束