[数据结构与算法]力扣113.路经总和2深度优先算法回溯

class Solution {
public:
    int sum=0;
    vector<vector<int>> ans;
    vector<int> track;
    void backtrack(TreeNode* root, int targetSum){
        if(root==nullptr) return;
        sum+=root->val;
        /*不要剪枝，因为节点有负数
        if(sum>targetSum){
            sum-=root->val;
            return;
        }
        */
        track.emplace_back(root->val);
        if(root->left==nullptr&&root->right==nullptr&&sum==targetSum){
            ans.emplace_back(track);
        }
        
        backtrack(root->left, targetSum);
        backtrack(root->right, targetSum);
        sum-=root->val;
        track.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(root==nullptr) return {};
        backtrack(root, targetSum);
        return ans;
    }
};

题目中故意给的样例都为正数，引诱你剪枝，其实还有负数的情况哈哈，聪明反被聪明误

超强干货来袭

云风专访：近40年码龄，通宵达旦的技术人生