Question

后序遍历的非递归算法是什么？

Answer 1

对于树的遍历我们最常用的三种遍历方法分别是前序遍历、中序遍历和后序遍历，使用的方法是深度优先遍历树的每一个节点，这些遍历方法都是使用递归函数来进行实现的。

在数据量大的情况下是比较低效的，原因在于系统帮助我们调用了一个栈并且做了诸如保护现场和恢复现场等复杂的操作。

才使得遍历可以使用非常简单的代码来实现，所以我们可以模仿系统中调用的栈自己可以来写一下栈，模仿其中的过程就可以完成对于三种遍历算法的实现，使用自定义的栈来代替系统栈可以得到效率上的提升，下面是对于后序遍历的非递归算法的实现。

简介

从逆后序遍历与先序遍历的关系中我们可以知道逆后序遍历序列为先序遍历交换左右子树的遍历顺序得到的。

所以我们得到了逆后序序列之后然后逆序就可以得到后序遍历的序列了，所以需要两个栈，第一个栈用来存储先序遍历交换左右子树的遍历的中介结果。