C++ solution using one stack. With detailed comment.


  • 0
    J
    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode *root) {
            vector<int> res;
            vector<TreeNode*> stack;
            TreeNode* temp, *node = root;
            while(node || !stack.empty()) {
                if(node) { // if we get a node, we push it to the stack and go to its left child
                    stack.push_back(node);
                    node = node->left;
                } else { // if we go to a NULL node, we have no node, so pop a node from stack
                    node = stack.back();
                    if(node->right) { // since the node was in the stack, its left child must already been visited. So only check right child. If it has right child, don't pop it, just go visit its right child first. BUT we also set its node->right to NULL, so when we see it again in the stack, we know that its right child has been visited.
                        temp = node;
                        node = node->right;
                        temp->right = NULL;
                    } else { // if the node in the stack has node->right==NULL, it either does not have a right child at all, or we have visited its right child already. Either way it's time to output the node and pop it from the stack. 
                        res.push_back(node->val);
                        stack.pop_back();
                        node = NULL;
                    }
                }
            }
            return res;
        }
    };

  • 0
    W

    Hi,
    It will work,but I think if you set temp->right = null, it would destroy the tree structure. I am not sure it is allowed or not.


Log in to reply
 

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