TIL a very elegant way for postorder traversal


  • 0
    H
    class Solution {
    public:
    	vector<int> postorderTraversal(TreeNode *root) {
    
    		vector<int> result;
    
    		stack<pair<TreeNode *, bool> > node_stack;
    		node_stack.push(make_pair(root, false));
    
    		while (!node_stack.empty())
    		{
    			bool isVisited = node_stack.top().second;
    			TreeNode *node = node_stack.top().first;
    			node_stack.pop();
    
    			if (node == NULL)
    			    continue;
    
    			if (isVisited)
    			{
    				result.push_back(node->val);
    			}
    			else
    			{
    				node_stack.push(make_pair(node, true));
    				node_stack.push(make_pair(node->right, false));
    				node_stack.push(make_pair(node->left, false));
    			}
    		}
    		return result;
    	}
    };
    

    Please pay attention to this:

    else
    {
         node_stack.push(make_pair(node, true));
         node_stack.push(make_pair(node->right, false));
         node_stack.push(make_pair(node->left, false));
    }
    

    if I change the push order, I can easily get preorder and inorder traversal. So just remember this one, you get three.


Log in to reply
 

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