145. Binary Tree Post Order Traversal

Given a binary tree, return thepostordertraversal of its nodes' values.

For example: Given binary tree{1,#,2,3},

   1
    \
     2
    /
   3

return[3,2,1].

Note:Recursive solution is trivial, could you do it iteratively?

Trivial Solution:

1. Recursion Call

2. Reverse the Binary Tree pre order traversal output

Thoughts:

1. Using stack: pshizhsysu generalized the tree traversal idea: O(n) in time and O(n) in space 1. For postorder traversal, we visit a node when popping it. last_pop represents the node which is popped the last time. For the top node in stack, it has three choices, pushing its left child in stack, or pushing its right child in stack, or being popped. If last_pop != top->left, meaning that its left tree has not been pushed in stack, then we push its left child. If last_pop == top->left, we push its right child. Otherwise, we pop the top node. 2. In contrast, for pre order traversal, we visit a node when pushing it in stack. For in order traversal, we visit a node when pushing its right child in stack.

2. Always use a lastNode, the (last node added to the answer), to keep track whether cur-> right is the same as that (if it is then, we need to visit the CurNode, if it is not, then we need to first visit cur->right)

3. Morris Traversal (Adopted from jianchaolifighter's Solution ) : O(n) in time and O(1) in space

Code 1:

/**
 * Definition for a binary tree node.
 * 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>answer;
    if (root == 0)
            return answer;
    stack<TreeNode*> s;
    s.push(root);    
    TreeNode* last_pop = root;
        while (!s.empty())
        {        
            TreeNode* top = s.top();
            if (top->left && top->left != last_pop && top->right != last_pop) // push_left
            {
                s.push(top->left);
            }
            else if (top->right && top->right != last_pop && (!top->left || top->left == last_pop)) // push_right
            {
                s.push(top->right);
            }
            else // pop
            {
                s.pop();
                last_pop = top;
                // cout << top->val << ' '; // visit top
                answer.push_back(top -> val);
            }
        }
    return answer;

    }
};

Code 1 by jianchaolifighter's solution:

/**
 * Definition for a binary tree node.
 * 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> answer;
        stack<TreeNode *> toVisit;
        TreeNode * nodeToLeft = root;
        TreeNode * lastNode = NULL; // You must assign NULL here as it will have some wired problems of not passing the 
                                    // case of "[1,null,2]"( I guess memory leak?)
        while(nodeToLeft || !toVisit.empty()){
            if(nodeToLeft){
                toVisit.push(nodeToLeft);
                nodeToLeft = nodeToLeft -> left;
            }
            else{
                TreeNode * topNode = toVisit.top();
                if(topNode -> right && lastNode != topNode -> right) 
                    nodeToLeft = topNode -> right;
                else {
                    answer.push_back(topNode->val);
                    lastNode = topNode;
                    toVisit.pop();
                }
            }
        }
        return answer;
    }
};

Code 2: Morris Traversal (hard):

1. Visit left subtree find the right the rightmost tree, add a cycle to the current node - left subtree - right most point

2. Iteratively creating cycles to the left (left) , until we detect a cycle, process the answer for the left subtree using three pointers, then move to the right subtree root, repeat 2 (right).

3. right subtree root and current node are included when cycle between right subtree - root, current node - and parent is detected ( reason why to add a dummy node as the root)

class Solution{
public:
    void reverseNodes(TreeNode* start, TreeNode* end) {
        // if (start == end) return;
        TreeNode* slow = start;
        TreeNode* fast = start -> right;
        TreeNode* fast_next;
        while (slow != end) {
            fast_next = fast-> right;
            // changing right
            fast -> right = slow;
            // increment
            slow = fast;
            fast = fast_next;
        }
    }
    void reverseAddNodes(TreeNode* start, TreeNode* end, vector<int>& nodes) {
        reverseNodes(start, end);
        TreeNode* node = end;
        while (true) {
            nodes.push_back(node -> val);
            if (node == start) break;
            node = node -> right;
        }
        reverseNodes(end, start);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> nodes;
        TreeNode* dump = new TreeNode (0);
        dump -> left = root;
        TreeNode* curNode = dump;
        while (curNode) {
            if (curNode -> left) {
            TreeNode* predecessor = curNode -> left;
            while (predecessor -> right && predecessor -> right != curNode)
            predecessor = predecessor -> right;
            if (!(predecessor -> right)) {
                // add right path
                predecessor -> right = curNode;
                curNode = curNode -> left;
            }
            else {
                // find a cycle, add left subtree 
                reverseAddNodes(curNode -> left, predecessor, nodes);
                // prune cycle path, finish left subtree, switch to the right  
                predecessor -> right = NULL;
                curNode = curNode -> right;
                }
            }
            else curNode = curNode -> right;
        }
        return nodes;
    }
};

Code 2 : Better Morris Traversal from Annie Kim's Blog