12ms DFS Solution


  • 1
    G
    class Solution {
    public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> res;
        vector<int> out;
        dfs(root,sum,res,out);
        return res;
    }
    
    void dfs(TreeNode* root,int cur_sum,vector<vector<int>> &res,vector<int>& out){
        if(!root) return;
        
        out.push_back(root->val);
        cur_sum-=root->val;
        if(!root->left&&!root->right&&cur_sum==0){
            res.push_back(out);
            return;
        }
        if(root->left){
            dfs(root->left,cur_sum,res,out);
            out.pop_back();
        }
        if(root->right){
            dfs(root->right,cur_sum,res,out);
            out.pop_back();
        }
    }
    };

  • 0
    S

    what is the necessity of out.pop_back? is it necessary to include it the program?


  • 0
    G

    yeah,it is necessary cause we use the method of backtracking, and the last node in one path must be removed before we searching for another path, otherwise the program may return a path with all nodes in the tree.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.