二叉树中和为某一值的路径

http://www.nowcoder.com/questionTerminal/b736e784e3e34731af99065031301bca

题目的主要信息：

题目给出我们一棵树的树根结点指针，和一个期待值
我们要找出这棵树中，从根节点到叶子节点的路径上的节点值之和等于该期待值的路径，找出所有这样的路径并返回。

举一反三：

学习完本题的思路你可以解决如下题目：

JZ82. 二叉树中和为某一值的路径（一）

JZ84. 二叉树中和为某一值的路径（三）

JZ86. 二叉搜索树的最近公共祖先

方法一：深度优先搜索（推荐使用）

知识点：深度优先搜索（dfs）

深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。

思路：

我们从根节点开始向左右子树进行递归，递归函数中需要处理的是：

当前的路径path要更新
当前的目标值expectNumber要迭代，减去当前节点的值
若当前节点是叶子节点，考虑是否满足路径的期待值，并考虑是否将路径添加到返回列表中

具体做法：

step 1：维护两个向量ret和path
step 2：编写递归函数dfs
step 3：递归函数内部要处理更新path，更新expectNumber，判断是否为叶子节点和判断是否要将path追加到ret末尾

图示： alt

Java实现代码：

import java.util.*;
public class Solution {
    private ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();
    
    void dfs(TreeNode root, int number) {
        // 处理树为空
        if (root == null) return;
        // 路径更新
        path.add(root.val);
        // number更新
        number -= root.val;
        // 如果递归当前节点为叶子节点且该条路径的值已经达到了expectNumber，则更新ret
        if(root.left == null && root.right == null && number == 0) {
            ret.add(new ArrayList<>(path));
        }
        // 左右子树递归
        dfs(root.left, number);
        dfs(root.right, number);
        path.removeLast();
    }
    
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        dfs(root, expectNumber);
        return ret;
    }
}

C++实现代码：

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    void dfs(TreeNode* root, int number) {
        // 处理树为空
        if (root == NULL) return;
        // 路径更新
        path.emplace_back(root->val);
        // number更新
        number -= root->val;
        // 如果递归当前节点为叶子节点且该条路径的值已经达到了expectNumber，则更新ret
        if(root->left == NULL && root->right == NULL && number == 0) {
            ret.emplace_back(path);
        }
        // 左右子树递归
        dfs(root->left, number);
        dfs(root->right, number);
        path.pop_back();
    }
    
    vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
        dfs(root, expectNumber);
        return ret;
    }
};

Python实现代码：

class Solution:
    def FindPath(self , root: TreeNode, target: int) -> List[List[int]]:
        ret, path = [], []
        def dfs(root: TreeNode, target: int):
            # 处理树为空
            if not root: return
            # 路径更新
            path.append(root.val)
            # 更新
            target -= root.val
            # 如果递归当前节点为叶子节点且该条路径的值已经达到了expectNumber，则更新ret
            if not root.left and not root.right and target == 0:
                ret.append(path[:])
            # 左右子树递归
            dfs(root.left, target)
            dfs(root.right, target)
            path.pop()
        dfs(root, target)
        return ret

复杂度分析：

时间复杂度： $O (n^{2})$ ，其中 $n$ 是树的节点数。最差情况下树的一半为链，一半为完全二叉树，并且所有的路径上的节点值之和都是expectedNumber，这样路径数量为 $O (n)$ ，且每条路径的节点数也为 $O (n)$ ，添加到ret的时间代价就是 $O (n^{2})$
空间复杂度： $O (n)$ ，递归栈的深度不会超过节点数量，但最大可能就是节点数量。

方法二：广度优先遍历（扩展思路）

知识点：队列

队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。