【力扣】113. 路径总和 II

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

递归+回溯

class Solution {
    private:
    vector<int> path;
    vector<vector<int>> result;
    void traversal(TreeNode* root,int targetSum){
        //终止条件
        if(root->left==nullptr&&root->right==nullptr&&targetSum==0){
            result.push_back(path);
            return;
        }
        if(root->left==nullptr&&root->right==nullptr) return;
        //递归
        if(root->left) {
            path.push_back(root->left->val);
            targetSum=targetSum-root->left->val;
            traversal(root->left,targetSum);//递归
            targetSum=targetSum+root->left->val;//回溯
            path.pop_back();//回溯
        }
        if(root->right) {
            path.push_back(root->right->val);
            targetSum=targetSum-root->right->val;
            traversal(root->right,targetSum);
            targetSum=targetSum+root->right->val;
            path.pop_back();
            
        }
        return;
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        result.clear();
        path.clear();
        if(root==nullptr) return result;
        path.push_back(root->val);//根
        traversal(root,targetSum-root->val);//左、右
        return result;
    }
};

递归+回溯

class Solution {
    private:
    vector<vector<int>> result;
    void dfs(TreeNode* root,vector<int> path,int sum){
        if(!root) return;
        path.push_back(root->val);
        if(!root->left&&!root->right&&sum==root->val){
            result.push_back(path);
        }
        if(root->left) dfs(root->left,path,sum-root->val);
        if(root->right) dfs(root->right,path,sum-root->val);
        path.pop_back();

    }

public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> path;
        dfs(root,path,targetSum);
        return result;     
    }
};

递归+回溯

class Solution {
    private:
    void dfs(TreeNode* root,vector<int> path,int sum,vector<vector<int>>& result){
        if(!root) return;
        path.push_back(root->val);
        if(!root->left&&!root->right&&sum==root->val){
            result.push_back(path);
        }
        if(root->left) dfs(root->left,path,sum-root->val,result);
        if(root->right) dfs(root->right,path,sum-root->val,result);
        path.pop_back();
    }

public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> path;
        vector<vector<int>> result;
        dfs(root,path,targetSum,result);
        return result;     
    }
};