二叉树中和为某一值路径

---

题目描述

输入一颗二叉树得根结点和一个整数，打印出二叉树中结点值得和为输入整数得所有路径。路径定义为从树得根结点开始往下一直到叶结点所经过得结点形成一条路径。

解题思路

深度优先搜索，采用前序遍历的方法。

可以通过设置两个容器，一个存放临时容器tmp结果，另一个result容器存放最终结果。

把当前的根结点存入tmp容器中，如果当前的根结点同时满足以下条件则说明是一条满足条件的路径：

• 输入的整数等于当前根结点的值；
• 当前根结点没有左子树；
• 当前根结点没有右子树；

其中后两个条件是题目中提到，根结点开始往下一直到 ** *叶结点*** 所经过的结点形成一条路径。

然后通过递归的方法判断左右子树。

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode (int x): val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
    vector<vector<int> > FindPath(TreeNode *root, int expectNumber)
    {
        if (root == NULL)
        {
            return result;
        }
        
        tmp.push_back(root->val);
        if (expectNumber-root->val==0 && root->left==NULL && root->right==NULL)
        {
            result.push_back(tmp);
        }
        FindPath(root->left, expectNumber - root->val);
        FindPath(root->right, expectNumber - root->val);
        
        tmp.pop_back();
        return result;
    }
private:
    vector<int> tmp;
    vector<vector<int>> result;
};

---

参考博文链接：https://cuijiahua.com/blog/2017/12/basis_24.html