A simple iterative solution with history stack for c++, 19ms


  • 2
    R

    Both stack and sumStack are for DFS. history stack records parents. When a new node has been visited, pop the history stack until finding his parent.

    class Solution
    {
    public:
    	vector<vector<int> > pathSum( TreeNode *root, int sum )
    	{
    
    		vector< vector<int>> res;
    		if ( root == NULL )
    			return res;
    
    		vector< TreeNode *> stack;
    		vector< TreeNode *> history;
    		vector< int> sumStack;
    		TreeNode *cur;
    		TreeNode *pre;
    		int tmp = 0;
    		stack.push_back( root );
    		sumStack.push_back( 0 );
    
    		while ( stack.size() ) {
    			cur  = stack.back();
    			stack.pop_back();
    
    			while ( history.size() > 0 ) {
    				pre = history.back();
    				if ( pre->left == cur || pre->right == cur )
    					break;
    				history.pop_back();
    			}
    
    			tmp = sumStack.back();
    			sumStack.pop_back();    
    			tmp = tmp + cur->val;
    			if ( tmp  == sum && cur ->right == NULL && cur->left == NULL ) {
    				vector< int> tmpv;
    				for ( int i = 0; i < history.size(); ++i ) {
    					tmpv.push_back( history[i]->val );
    				}
    				tmpv.push_back(cur->val);
    				res.push_back( tmpv );
    				continue;
    			}
    
    			history.push_back( cur );
    			if ( cur->right ) {
    				stack.push_back( cur->right );
    				sumStack.push_back( tmp );
    			}
    			if ( cur->left ) {
    				stack.push_back(  cur->left );
    				sumStack.push_back( tmp );
    			}
    		}
    		return res;
    	}
    };

Log in to reply
 

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