Simple DFS C++ solution


  • 0
    M
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    private:
        void _pathSum(TreeNode* root, int sum, int level, vector<vector<int>>& paths, vector<int> &path)
        {
            if(root == NULL)
                return;
            if(level == path.size())
            {
                path.push_back(root->val);
            }
            else
            {
                path[level] = root->val;
            }
            
            if(root->left == NULL && root->right == NULL && sum-root->val == 0)
            {
                vector<int> temp(path.begin(),path.begin()+level+1);
                paths.push_back(temp);
            }
            
            _pathSum(root->left,sum-root->val,level+1,paths,path);
            _pathSum(root->right,sum-root->val,level+1,paths,path);
            
        }
    public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            
            vector<int> path;
            vector<vector<int>> paths;
            if(root == NULL)
                return paths;
            int level = 0;
            _pathSum(root,sum,level,paths,path);
            
            return paths;
        }
    };
    

Log in to reply
 

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