剑指offer-25.二叉树中和为某一值的路径

0 题目

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

1 分析

深度优先遍历+回溯.

出点就是，当target==0，且节点没有子树的时候。

    vector<vector<int>> FindPath(TreeNode *root, int target)
    {
        vector<vector<int>> ret;
        vector<int> tmp;
        aux(root, target, tmp, ret);
        return ret;
    }

    void aux(TreeNode *root, int target, vector<int> &tmp, vector<vector<int>> &ret)
    {
        if (root != nullptr)
        {
            tmp.push_back(root->val);

            if (target - root->val == 0 && root->left == nullptr && root->right == nullptr)
            {
                ret.push_back(tmp);
                // 这里pop的原因在于，下面需要return ，如果不pop会影响和偶棉的结果
                tmp.pop_back();
                return;
            }

            aux(root->left, target - root->val, tmp, ret);
            aux(root->right, target - root->val, tmp, ret);
            tmp.pop_back();
        }
    }