题解 | #二叉树根节点到叶子节点和为指定值的路径#
二叉树根节点到叶子节点和为指定值的路径
http://www.nowcoder.com/practice/840dd2dc4fbd4b2199cd48f2dadf930a
算法思想一：回溯法（先序遍历）
解题思路：
使用回溯法解决，其包含 先序遍历 + 路径记录 两部分
先序遍历： 按照 “根、左、右” 的顺序，遍历树的所有节点。
路径记录： 在先序遍历中，记录从根节点到当前节点的路径。当路径为根节点到叶节点形成的路径且各节点值的和等于目标值 sum 时，将此路径加入结果列表。
路径记录： 在先序遍历中，记录从根节点到当前节点的路径。当路径为根节点到叶节点形成的路径且各节点值的和等于目标值 sum 时，将此路径加入结果列表。
算法流程：
pathSum(root, sum) 函数：
初始化： 结果列表 res ，路径列表 path 。
返回值： 返回 res 即可。
pathSum(root, sum) 函数：
初始化： 结果列表 res ，路径列表 path 。
返回值： 返回 res 即可。
recur(root, tar) 函数：
递推参数： 当前节点 root ，当前目标值 tar 。
终止条件： 若节点 root 为空，则直接返回。
递推工作：
1、路径更新： 将当前节点值 root.val 加入路径 path ；
2、目标值更新： tar = tar - root.val（即目标值 tar 从 sum 减至 0 ）；
3、路径记录： 当 root 为叶节点 且路径和等于目标值 ，则将此路径 path 加入 res 。
4、先序遍历： 递归左 / 右子节点。
5、路径恢复： 向上回溯前，需要将当前节点从路径 path 中删除，即执行 path.pop()
图解：
代码展示:
Python版本
class Solution: def pathSum(self , root , sum ): # write code here # 初始化 返回数组 路径数组 res, path = [], [] def recur(root, tar): if not root: return path.append(root.val) tar -= root.val if tar == 0 and not root.left and not root.right: # 路径符合要求 加入res res.append(list(path)) # 递归 左右子树 recur(root.left, tar) recur(root.right, tar) path.pop() # 回溯 recur(root, sum) return res
复杂度分析：
时间复杂度 O(N) ： N 为二叉树的节点数，先序遍历需要遍历所有节点。空间复杂度 O(N) ： 最差情况下，即树退化为链表时，path 存储所有树节点，使用 O(N) 额外空间。
算法思想二：递归
解题思路：
从根节点到叶子节点遍历他所有的路径，返回他所有路径中和等于sum的节点，这里有两种实现方式，一种是减，一种是加。减就是从根节点开始，用sum不断的减去遍历到的每一个节点，一直到叶子节点，在减去叶子节点之前查看sum是否等于叶子节点，如果等于说明我们找到了一组 图解：
此解题思路图解和采用先序遍历同样思想，唯一区别在于此方法在递归的时候没有依次移除 subList 存储的节点
代码展示：
JAVA版本
public class Solution {
/**
*
* @param root TreeNode类
* @param sum int整型
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
// write code here
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
dfs(root, sum, new ArrayList<>(), result);
return result;
}
public void dfs(TreeNode root, int sum, ArrayList<Integer> list,
ArrayList<ArrayList<Integer>> result) {
//如果节点为空直接返回
if (root == null)
return;
//因为list是引用传递，为了防止递归的时候分支污染，我们要在每个路径
//中都要新建一个subList
ArrayList<Integer> subList = new ArrayList<>(list);
//把当前节点值加入到subList中
subList.add(new Integer(root.val));
//如果到达叶子节点，就不能往下走了，直接return
if (root.left == null && root.right == null) {
//如果到达叶子节点，并且sum等于叶子节点的值，说明我们找到了一组，
//要把它放到result中
if (sum == root.val)
result.add(subList);
//到叶子节点之后直接返回，因为在往下就走不动了
return;
}
//如果没到达叶子节点，就继续从他的左右两个子节点往下找，注意到
//下一步的时候，sum值要减去当前节点的值
dfs(root.left, sum - root.val, subList, result);
dfs(root.right, sum - root.val, subList, result);
}
} 复杂度分析：
时间复杂度 O(N) ： N 为二叉树的节点数，递归遍历所有节点。空间复杂度 O(N) ： 最差情况下，即树退化为链表时，subList 存储所有树节点，使用 O(N) 额外空间。
Momenta公司福利 296人发布