Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal 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?

思路：

树的遍历首先想到的一定是递归。

迭代版本的程序，需要引入prev指针和cur指针，cur指针指向栈顶节点。根据左右子节点入堆栈的不同方式有两种做法。

解法一是无论任何情况，总是先入右子节点后入左子节点。这样的话prev和cur的关系就分为：

1. prev->left == cur || prev->right == cur（从上往下，还未到达树的底部）
2. cur->left == prev（因为堆栈先入右子节点后入左子节点，这种情况意味着完成左子树，没有右子树）
3. cur->right == prev （完成右子树遍历）
4. any other （完成左子树，下一步遍历右子树）

解法二是有左子节点的时候只入左子节点，完成左子节点才入右子节点。这也是Leetcode官网上的答案（链接点这里）。这种方法的好处就是prev和cur的关系比较清晰：

1. 从上往下未达到树底部
2. 完成左子树
3. 完成右子树

解法三。根据解法一，优化之后，发现问题可以简化为考虑节点何时出栈何时入栈。于是我们有了解法三：

• 何时出栈？

1. 当前节点为叶子节点
2. 完成左子树遍历，没有右子树，隐含条件prev不为空。
3. 完成右子树遍历，隐含条件prev不为空。

• 何时入栈? 不出栈时，先入右子节点后入左子节点。

代码如下：