思路分析
这类水题就是考察二叉树的中序遍历而已。当然，递归遍历的方法是个人都会写，但是非递归遍历，如果没有刻意背过的话，恐怕很容易就忘掉了。
于是直接在网上copy了一份非常容易记住的，非递归遍历的代码，并且做到了以三种方式遍历二叉树时，可以保证代码的整体结构是一样的，仅仅需要更改局部几个入栈次序而已。实测的时间复杂度也非常令人满意，实在是神器啊……
代码
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> res;
stack<pair<TreeNode *, bool> > stk;
stk.push(make_pair(root, false));
while ( !stk.empty() ) {
TreeNode *cur = stk.top().first;
bool flag = stk.top().second;
stk.pop();
if ( cur == NULL ) continue;
if ( flag ) {
res.push_back(cur->val);
} else {
//只需要更改这里的入栈次序
//此时为后序遍历
stk.push(make_pair(cur, true));
stk.push(make_pair(cur->right, false));
stk.push(make_pair(cur->left, false));
}
}
return res;
}
};