找出所有根结点到叶子节点之和为sum的路径

---

题目描述

给定一个二叉树和一个值sum，请找出所有根结点到叶子结点值之和等于sum的路径。

解题思路

这个和判断是否又满足根结点到叶子结点之和为sum的相似，只是需要输出满足条件的路径，而且还需找出所有路径。

首先，构造一个子函数实现遍历二叉树，找出满足条件的所有路径。

• 构造vector<vector<>>容器result来存放路径；构造vector容器res来存放当前遍历的结点值；
• 判断当前是否满足根结点到叶子节点的路径，且结点值之和为sum（sum的值会随着递归的调用而减小，每次减小的部分就是当前结点的值）；
  • 若满足条件，则将此路径存放到result中，否则继续下一步；
• 然后调用递归，以当前结点的左结点为根结点，寻找符合条件的路径；
• 当左树部分寻找完后，调用递归，以当前根结点的右结点为根，寻找符合条件的路径；

如果没有解释清楚，请看代码吧！:joy:

代码

//树的结构定义参见源代码
class Solution
{
public:
    vector<vector<int> > pathSum(TreeNode* root, int sum)
    {
        if (!root)
            return result;
        vector<int> res;
        path(root, sum, res);
        return result;
    }
    
private:
    vector<vector<int> > result;
    void path(TreeNode* root, int sum, vector<int> res)
    {
        if (!root)
            return ;
        res.push_back(root->val);
        if (root->left == NULL && root->right == NULL && root->val == sum)
            result.push_back(res);
        
        path(root->left, sum - root->val, res);
        path(root->right, sum - root->val, res);
    }
};

注意，每调用依次path函数，res容器就会重新构造一次，以满足每条路径都在各自的容器内。

参考链接：https://www.nowcoder.com/questionTerminal/840dd2dc4fbd4b2199cd48f2dadf930a?f=discussion