C++, 12ms Recursion solution and 16ms Loop solution with stack


  • 0
    C
    class Solution {
    public:
    	void pathSum_core(TreeNode* root,int cursum,vector<vector<int>>& res, vector<int>& curpath)
    	{
    		if (root == NULL)
    			return;
    		curpath.push_back(root->val);
    		cursum -= root->val;
    		if (root->left == NULL&&root->right == NULL&&cursum==0)
    			res.push_back(curpath);
    		else
    			{
    		        pathSum_core(root->left,cursum, res, curpath);
    		        pathSum_core(root->right, cursum, res, curpath);
    			}
    		curpath.pop_back();
    		cursum += root->val;
    		return;
    	}
    	vector<vector<int>> pathSum(TreeNode* root, int sum) {
    		vector<vector<int>> res;
    		vector<int> curpath;
    		pathSum_core(root, sum,res, curpath);
    		return res;
    	}
    };

  • 0
    C
    class Solution {
    public:
    	vector<vector<int>> pathSum(TreeNode* root, int sum) {
    		vector<vector<int>> res;
    		if (root == NULL)
    			return res;
    		stack<TreeNode*> s;
    		vector<int> curpath;
    		int stacksum = 0;
    		TreeNode *pcur=root, *plast=NULL;
    		while (pcur || !s.empty())
    		{
    			while (pcur)
    			{
    				s.push(pcur);
    				curpath.push_back(pcur->val);
    				stacksum += pcur->val;
    				pcur = pcur->left;
    			}
    			pcur = s.top();
    			if (pcur->left == NULL&&pcur->right == NULL&&sum == stacksum)
    				res.push_back(curpath);
    			if (pcur->right&&pcur->right != plast)
    				pcur = pcur->right;
    			else
    			{
    				stacksum -= pcur->val;
    				s.pop();
    				curpath.pop_back();
    				plast = pcur;
    				pcur = NULL;
    			}
    		}
    		return res;
    	}
    };

  • 0
    X
    class Solution {
    public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            vector<vector<int> > res;
            vector<int> path;
            genPath(res,path,root,sum);
            return res;
        }
    
    private:
        void genPath(vector<vector<int> > &res,vector<int> path,TreeNode* root, int sum){
            if(!root) return;
            path.push_back(root->val);
            if(root->val == sum && !root->left && !root->right){
                res.push_back(path);
                return;
            }
            genPath(res,path,root->left,sum-root->val);
            genPath(res,path,root->right,sum-root->val);
        }
    };

Log in to reply
 

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