Binary Tree Postorder Traversal

 
 
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  /*
  class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
      vector<int> output;
      if (!root) return output;
       
       TreeNode *prev = NULL;   
       stack<TreeNode *> st;
       st.push(root);
       while(!st.empty())
       {
           TreeNode *cur = st.top();
           
           if (prev == NULL || prev->left == cur || prev->right == cur)
           {
               if (cur->left) {
                    st.push(cur->left);
                  } else if (cur->right) {
                    st.push(cur->right);
                  } else {
                     output.push_back(cur->val);
                    st.pop();
                  }
           }
           else if (cur->right == prev) {
               st.pop();
               output.push_back(cur->val);
              
           }
           else if (cur->left == prev) {
               if (cur->right) {
                   st.push(cur->right);
               }
               else {
                   st.pop();
                   output.push_back(cur->val);
                   
               }
           }
            prev = cur;
       }
       
       return output;
    }
};
*/

    /*Method 1
    vector<int> postorderTraversal(TreeNode *root) {
      vector<int> output;
      if (!root) return output;
       
       TreeNode *prev = NULL;   
       stack<TreeNode *> st;
       st.push(root);
       while(!st.empty())
       {
           TreeNode *cur = st.top();
           if (!cur->left && !cur->right) {
               output.push_back(cur->val);
               st.pop();
           }
           if (cur->right) {
              st.push(cur->right);
              cur->right= NULL;
           }
           if (cur->left) {
              st.push(cur->left);
              cur->left = NULL;
           }
       }
       
       return output;
    } 
    
    // Method 2
    vector<int> postorderTraversal(TreeNode *root) {
      vector<int> output;
      if (!root) return output;
       
       TreeNode *prev = NULL;   
       stack<TreeNode *> st;
       stack<TreeNode *> st2;
       st.push(root);
       while(!st.empty())
       {
           TreeNode *cur = st.top();
           st.pop();
           st2.push(cur);
           if (cur->left) 
              st.push(cur->left);
           if (cur->right)
              st.push(cur->right);
       }
       
       while(!st2.empty()){
           TreeNode *cur = st2.top();
           st2.pop();
           output.push_back(cur->val);
       }
       return output;
    }
    
    // Method 3
    vector<int> postorderTraversal(TreeNode *root) {
      vector<int> output;
       stack<TreeNode *> st;
       while(!st.empty() || root)
       {
           if (!root)
           {
              while(!st.empty() && root==st.top()->right)
              {
                  root= st.top();
                  st.pop();
                  output.push_back(root->val);
              } 
              root= st.empty()? NULL : st.top()->right;
           }
           else 
           {
               st.push(root);
               root = root->left; 
           }
       }
       
       return output;
    }
    */
    
    // Simple coder's solution
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> output;
        stack<TreeNode*> st;
      
        TreeNode *prev = NULL;  
        pushLeft(root, st);
        while (!st.empty()) {
            root = st.top();
            if (prev == root->left && root->right)
            {
               pushLeft(root->right, st);
               prev = NULL;
            }
            else
            {
                output.push_back(root->val);
                st.pop();
                prev = root;
            }
        }

        return output;
    }
    
   void pushLeft(TreeNode *root, stack<TreeNode *> &st)
   {
       while(root) {
           st.push(root);
           root = root->left;
       }
   }
};