Question

二叉树的后序遍历，非递归

如果只用一个堆栈，且不记录节点的标志位（比如有没有访问过左/右子树），能实现吗？
（大致说下思路就行）
不是线索树，没有头节点，只有指向根节点的指针；某个节点没有左/右子树那个指针就是NULL

Answer 1

后序遍历的非递归步骤类似于中序遍历，在遍历左子树前将根结点指针送入栈中
但是左子树遍历完成后，无法访问根结点，只有在右子树遍历完后，才能访问根结点

如果不使用标志位区分第几次到达根结点，可以利用如下的后序遍历特征来完成：
当栈顶元素(根)的右子树为空(即：无右孩子)，或者是右子树非空但是已遍历完，即右孩子恰好是刚才访问过的结点，此时应访问栈顶结点，并在访问后退栈
否则，如果栈顶元素的右孩子非空且未遍历，此时直接访问栈顶元素的右孩子而不退栈

算法要点只是需要记住最近访问过的结点即可，也就是每次访问一个结点后，就记住这个结点