c++ solution with one stack


  • 0
    vector<int> postorderTraversal(TreeNode* root) 
    {
        vector<int> result;
        TreeNode* visit_node = root;
        TreeNode* peek_node = NULL;
        TreeNode* last_visit_node = NULL;
        stack<TreeNode*> tree_nodes;
        
        while ((visit_node != NULL) || !tree_nodes.empty())
        {
            if (visit_node != NULL)
            {
                tree_nodes.push(visit_node);
                visit_node = visit_node->left;
            }
            else
            {
                peek_node = tree_nodes.top(); // peek first node in stack
                if ((peek_node->right != NULL) && (peek_node->right != last_visit_node))
                {
                    visit_node = peek_node->right;
                }
                else
                {
                    last_visit_node = peek_node;
                    tree_nodes.pop();
                    result.push_back(last_visit_node->val);
                }
            }
        }
        
        return result;
    }

Log in to reply
 

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