C++ DFS Solution--Easy to Understand


  • 0
    M
    class Solution {
    public:
        vector<vector<int>> paths;
        void getPathSum(TreeNode* root, int sum, vector<int> path, int res){
            
            if( root == NULL){
                return;
            }
    
            //Keeps track of the current path
            path.push_back(root->val);
            sum += root->val;
    
            //Depth first traversal
            getPathSum(root->left, sum, path, res);
            getPathSum(root->right, sum, path, res);
    
            //Gotcha! Found a path
            if(root->left == NULL && root->right == NULL && res == sum){
                paths.push_back(path);
                return;
            }
        }
    
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            vector<int> path;
            int tmp = 0;
            getPathSum(root, tmp, path, sum);
            
            return paths;
        }
    };

Log in to reply
 

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