之前整理过非递归方式遍历二叉树的后序遍历的方式，先简单回顾一下：
第一种思路：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。
第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
由于接下来会用到先序遍历，所以，我们顺便回忆一下先序遍历的非递归算法：
对于任一结点P：
(1)访问结点P，并将结点P入栈;
(2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;
(3)直到P为NULL并且栈为空，则遍历结束。
不过现在看考研书，书中提供了一种新的思路，之前完全没有想到：
对于上面的二叉树，我们可以写出它的前序遍历方式：
A,B ,D,G,C,E,F
其后序遍历方式为：
G,D,B,E,F,C,A
如果我们把后序遍历逆序：
A,C,F,E,B,D,G
仔细看一看，我想你一定已经发现规律了，如果我们把后序遍历逆序后的结果称为逆后序遍历，那么逆后序遍历只不过是先序遍历过程中对左右子树遍历顺序交换所得到的结果。
因此，只需要将先序遍历的非递归算法中对左右子树的遍历顺序交换就可以得到逆后序遍历的序列，然后再将逆后序遍历的结果逆序就得到了后序遍历的结果，因此我们需要两个栈，一个栈stack1用于辅助做逆后序遍历，并将遍历结果序列压入另一个栈stack2，然后将stack2的元素全部出栈，所得到的序列就是后序遍历的结果。
