Binary Tree Postorder Traversal

非递归的陷阱：

 if (current->right == NULL || current->right == lastVisited)

如果没有限制current->right == lastVisited，就会导致死循环。

  1
 / \
2   3

首先访问 2，然后访问 3， 接着访问 1 ， 然后 1->right != NULL ,就死循环了。

/**
 * 本代码由九章算法编辑提供。没有版权欢迎转发。
 * - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
 * - 现有的面试培训课程包括：九章算法班，系统设计班，BAT国内班
 * - 更多详情请见官方网站：http://www.jiuzhang.com/
 */

// non-recursion version 

/**
 * 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> result;
        stack<TreeNode *> myStack;

        TreeNode *current = root, *lastVisited = NULL;
        while (current != NULL || !myStack.empty()) {
            while (current != NULL) {
                myStack.push(current);
                current = current->left;
            }
            current = myStack.top(); 
            if (current->right == NULL || current->right == lastVisited) {
                myStack.pop();
                result.push_back(current->val);
                lastVisited = current;
                current = NULL;
            } else {
                current = current->right;
            }
        }
        return result;
    }
};

双栈法

 vector<int> postorderTraversal(TreeNode* root) {
         //double stack 
         stack<TreeNode*>stk;
           stack<TreeNode*>stk2;
         vector<int>res;
         if(root == NULL) return res;
         stk.push(root);
         while(!stk.empty()){
             TreeNode *curr = stk.top();
             stk2.push(curr);
             stk.pop();
             if(curr->left != NULL) stk.push(curr->left);
             if(curr->right != NULL) stk.push(curr->right);
         }
         while(!stk2.empty()){
            res.push_back(stk2.top()->val); 
            stk2.pop();
         }
         return res;
    }