题解 | #二叉树根节点到叶子节点和为指定值的路径#

二叉树根节点到叶子节点和为指定值的路径

http://www.nowcoder.com/practice/840dd2dc4fbd4b2199cd48f2dadf930a

算法思想一：回溯法（先序遍历）

解题思路：

使用回溯法解决，其包含先序遍历 + 路径记录两部分

先序遍历：按照 “根、左、右” 的顺序，遍历树的所有节点。
路径记录：在先序遍历中，记录从根节点到当前节点的路径。当路径为根节点到叶节点形成的路径且各节点值的和等于目标值 sum 时，将此路径加入结果列表。

算法流程：
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);
    }
}