c++ DFS + Backtrack


  • 0
    G
    
    class Solution {
    public:
        void pathSumHelper(TreeNode* root, int sum, vector<vector<int>>& result, vector<int>& curPath)
        {
            if(root->left == nullptr && root->right == nullptr)
            {
                if(sum == root->val)
                {
                    curPath.push_back(root->val);
                    result.push_back(curPath);
                    curPath.pop_back();
                }
            }
            else
            {
                if(root->left != nullptr)
                {
                    curPath.push_back(root->val);
                    pathSumHelper(root->left, sum - root->val, result, curPath);
                    curPath.pop_back();
                }
                if(root->right != nullptr)
                {
                    curPath.push_back(root->val);
                    pathSumHelper(root->right, sum - root->val, result, curPath);
                    curPath.pop_back();
                }
            }
        }
        
        vector<vector<int>> pathSum(TreeNode* root, int sum) 
        {
            vector<vector<int>> result;
            if(root == nullptr)
            {
                return result;
            }
            vector<int> curPath;
            pathSumHelper(root, sum, result, curPath);
            return result;
        }
    };
    

Log in to reply
 

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