题解 | #二叉树中和为某一值的路径(二)#

第十九题 递归调用 解决 不断获取子树的符合要求的路径，并添加上当前结点的值

是十八题的复杂版本 不只要求判断有没有路径 要想办法 找到所有的路径并保存下来

第一个代码 稍微长一点 从根节点开始，更好理解

第二段代码是对第一个代码的化简 删除了重复的代码

/*
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) {
        // 和上一题找结点类似
        vector<vector<int>> temp;
        vector<vector<int>> ret_ans;
        // 两个边界情况 第二个就是 单独只有一个根节点 正好是要求的值
        if(root == NULL)
            return temp;
        
        // 后面子树要的sum的和 是要求的总sum 减去当前结点的值
        int sum=expectNumber-root->val;
        if(sum==0 && root->left==NULL && root->right==NULL)
        {
            vector<int> one;
            one.push_back(root->val);
            ret_ans.push_back(one);
            return ret_ans;
        }
        
        // 如果有左（右）孩子，就递归调用左（右）孩子
        if(root->left!= NULL){
            temp=find_path(root->left,sum);
            ret_ans.insert(ret_ans.end(), temp.begin(),temp.end());
        }
        if(root->right!=NULL){
            temp=find_path(root->right,sum);
            ret_ans.insert(ret_ans.end(), temp.begin(),temp.end());
        }
        
        // 对返回的结果进行处理，加上当前这一层结点的值
        if(!ret_ans.empty())
        {
            for(int i=0;i<ret_ans.size();i++)
            {
                ret_ans[i].push_back(root->val);
            }
        }
        
        // 反转所有的结果 要求是输出从根结点开始的容器
        for(int i=0;i<ret_ans.size();i++)
        {
            reverse(ret_ans[i].begin(),ret_ans[i].end());
        }
        return ret_ans;
    }
    
    // 递归调用
    vector<vector<int>> find_path(TreeNode* root,int sum)
    {
        vector<vector<int>> ret_ans;
        if(root==NULL)
            return ret_ans;
        sum=sum-root->val;
        
        // 同上一题的判断条件
        // 当sum成了0 并且是叶子结点，说明结果正确 返回true
        if(sum==0 && root->left==NULL && root->right==NULL)
        {
            vector<int> oneans;
            oneans.push_back(root->val);
            ret_ans.push_back(oneans);
            return ret_ans;
        }
        
        // temp临时保存访问子树得到的结果
        vector<vector<int>> temp;
        
        // 当不是叶子结点 则要继续往下去左右子树递归调用
        // 返回的结果是左右子树 到根节点值为sum的容器，将容器保存到ret_ans中
        if(root->left!=NULL){
            temp=find_path(root->left,sum);
            ret_ans.insert(ret_ans.end(), temp.begin(),temp.end());
        }
        if(root->right!=NULL){
            temp=find_path(root->right,sum);
            ret_ans.insert(ret_ans.end(), temp.begin(),temp.end());
        }
        // 如果有结果，则ret_ans要加上当前这一层的值
         if(!ret_ans.empty())
        {
            for(int i=0;i<ret_ans.size();i++)
            {
                ret_ans[i].push_back(root->val);
            }
        }
        
        return ret_ans;
    }
};



第二个代码 化简版本

/*
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) {
        // 和上一题找结点类似
        vector<vector<int>> temp;
        vector<vector<int>> ret_ans;
        // 两个边界情况 第二个就是 单独只有一个根节点 正好是要求的值
        if(root == NULL)
            return temp;
        // 直接全部扔下去递归调用 不需要判断root有没有左右子树 而是将root直接扔下去计算
        // 因为 find_path函数的代码 和之前写的判断根节点的代码完全一致
        ret_ans=find_path(root, expectNumber);
        // 反转所有的结果 要求是输出从根结点开始的容器
        for(int i=0;i<ret_ans.size();i++)
            reverse(ret_ans[i].begin(),ret_ans[i].end());
        return ret_ans;
    }
    
    // 递归调用
    vector<vector<int>> find_path(TreeNode* root,int sum)
    {
        vector<vector<int>> ret_ans;
        if(root==NULL)
            return ret_ans;
        sum=sum-root->val;
        
        // 同上一题的判断条件
        // 当sum成了0 并且是叶子结点，说明结果正确 将这个结点 装入一维数组 添加到ret_ans中
        // 后面 收到的结果 在这个结点之上，继续补充路径上的val
        if(sum==0 && root->left==NULL && root->right==NULL){
            vector<int> oneans;
            oneans.push_back(root->val);
            ret_ans.push_back(oneans);
            return ret_ans;
        }
        
        // temp临时保存访问子树得到的结果
        vector<vector<int>> temp;
        
        // 当不是叶子结点 且还有左（右）子树，则要继续往下去递归调用左右子树
        // 返回的结果是左右子树 到根节点值为sum的容器，将容器保存到ret_ans中
        if(root->left!=NULL){
            temp=find_path(root->left,sum);
            ret_ans.insert(ret_ans.end(), temp.begin(),temp.end());
        }
        if(root->right!=NULL){
            temp=find_path(root->right,sum);
            ret_ans.insert(ret_ans.end(), temp.begin(),temp.end());
        }
        
        // 如果有结果，则ret_ans要加上当前这一层的值
         if(!ret_ans.empty())
            for(int i=0;i<ret_ans.size();i++)
                ret_ans[i].push_back(root->val);
        
        return ret_ans;
    }
};