Sharing my implementation and looking for an even more concise one.


  • 13
    S

    I have checked many implementations of iterative solutions to this problem; many of them seem to be rather verbose. After some investigations, I have come up with this following solution:

    vector<int> postorderTraversal(TreeNode *root) {
        stack<TreeNode*> s;
        TreeNode* cur = root;
        vector<int> temp;
        while(true)
        {
            if (cur == NULL)  // If the current branch is finished, then go back to the most recent unvisited branch
            {
                if (!s.empty()) {cur = s.top(); s.pop(); continue;} // Checked the first unvisited branch
                else break;
            }
            temp.push_back(cur->val); // Add the current value to the FRONT of list
            s.push(cur->left);         // Push the left child to the stack
            cur = cur->right;          // Go the right child
        }
        // Don't forget to reverse the 'right-to-left' pre-order traversal!
        return vector<int>(temp.rbegin(), temp.rend()); 
    }
    

    The idea is to exploit the fact that Post-order Traversal is equivalent to the REVERSE of a 'right-to-left' (i.e. traverse the right children then the left ones) pre-order traversal. For example, for the following tree:

           A
          / \
         B   C
        / \
       D   E
    

    post-order: D E B C A

    'right-to-left' pre-order: A C B E D

    As for the pre-order traversal, we initialize the current node to the root. Then we keep adding the value of the current node to the traversal list, and then push its left child to a stack, and set its right child as the current node. That way, each element in the stack represents the root of a branch that we should visit at later time, with the top element being the first one that we visit as soon as we get the chance to.

    If we find the current node is NULL, it means we have reached the end of a branch, then we should visit a new branch beginning at the top of the stack. If the top element of the stack is also NULL, it means this branch does not contain anything, then we should pop it out, then check the new top element until it is no longer NULL. If the stack turns empty before we find a non-NULL node in it, then we have visited all the nodes in the tree.

    And it boils down to this simple iterative rule:


    In each iteration

    1. If the current node is not NULL, then

    A) add its value to the traversal list, and

    B) push its LEFT child to stack, and

    C) go to its RIGHT child.

    1. If the current node is NULL, then set the current node to the top of the stack (terminate if the stack is already empty).

    Implementation-wise, this is the most concise solution I have come up so far. And the code can be applied almost directly to a similar problem ('Binary Tree Pre-Order Traversal') with little modification.
    I really would like to know if there is any better algorithm that would result in an even more concise implementation than this one. Any comments/suggestions are welcome!


  • 0
    A

    wouldn't a two stack solution be simpler? one stack for the tree node to keep track of the traversal, another stack for the values visited.


  • 1
    X

    checkout my solution. :)

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> ret;
        if (root == NULL)
            return ret;
    
        stack<TreeNode *> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode *cur = s.top();
            s.pop();
            ret.push_back(cur->val);
            if (cur->left != NULL)
                s.push(cur->left);
            if (cur->right != NULL)
                s.push(cur->right);
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
    

  • 0

    Excellent idea, reversing the preorder!

    I prefer to just put both children on the stack so that the stack is the only source. I think it makes the logic simpler:

    vector<int> postorderTraversal(TreeNode *root) {
        stack<TreeNode*> s;
        s.push(root);
        vector<int> temp;
        while (s.size()) {
            TreeNode* cur = s.top();
            s.pop();
            if (cur != NULL) {
                temp.push_back(cur->val);
                s.push(cur->left);
                s.push(cur->right);
            }
        }
        return vector<int>(temp.rbegin(), temp.rend()); 
    }
    

    Though if you really want concise, you better switch languages :-P
    Here's Python:

    def postorderTraversal(self, root):
        s, temp = [root], []
        while s:
            cur = s.pop()
            if cur:
                temp += cur.val,
                s += cur.left, cur.right
        return temp[::-1]

Log in to reply
 

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