Using not recursive postorder solution, c++,16ms.


  • 0
    R
    vector<vector<int>> pathSum(TreeNode* root, int sum) 
    {
    	vector<vector<int>> result ;
    	vector<int> tempData;
    	vector<int> flag ;
    	stack<TreeNode*> saveTree;
    	while (root || saveTree.empty() != true)
    	{
    		while (root)
    		{
    			sum -= root->val;
    			tempData.push_back(root->val);
    			flag.push_back(0);
    			saveTree.push(root);
    			root = root->left;
    		}
    
    		while (flag.size() != 0 && flag.back() == 1 )
    		{
    			TreeNode* temp = saveTree.top();
    			if(sum == 0 && temp->left == NULL && temp->right == NULL)
    				result.push_back(tempData);
    			sum += temp->val;
    			tempData.pop_back();
    			saveTree.pop();
    			flag.pop_back();
    		}
    		if(saveTree.size() != 0)
    		{
    			root = saveTree.top();
    			root = root->right;
    			flag[flag.size() -1 ] = 1;
    		}
    	}
    	return result;
    }

Log in to reply
 

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