二叉树的前序中序后序遍历非递归版本

summary

:

面试中经常会让你写出三种遍历中的一种的非递归版本，通常是中序遍历和后序遍历，前序 遍历很少，因为前序遍历毕竟比较简单。

以我的智商，没有做过的话，只能想出来前序遍历的非递归版本，而中序遍历和后序遍历则 是绞尽脑汁都想不出来。最终参考了别人的做法，才理解并写出来了，算是记忆，估计再过 一段时间我又忘了。不过到时可以翻开我的这篇文章看看。

前序遍历

这个是最简单的。用一个栈存储节点，先输出栈顶元素的值，再把左右孩子的节点入栈（如 果有的话）。由于在遍历的时候是先遍历左子树再遍历右子树，那么反过来，在入栈的时候， 就先把右孩子入栈，再把左孩子入栈。

中序遍历

有难度。得先从根节点开始，不断把左边的孩子入栈，直到没有为止。然后取栈顶节点， 这个时候就不用管这个节点的左子树了，因为左子树已经全部处理了 ，直接输出 这个节点的值，然后看这个节点是否有右孩子，有的话把右子树像根节点一样处理，不断 把左孩子入栈，重复上面的操作，没有的话则继续处理下一个栈顶的节点。

后序遍历

最难。关键在于，当要输出某个节点时，怎么判断它的左右子树都已经处理。中序遍历不用 判断左子树是否已经处理，因为预先处理了，从栈顶拿的节点的左子树肯定处理的了。现在 要怎么办呢？我们知道，在后序遍历中，根节点是最后一个访问的，那么在根节点的上面， 要么是它的右孩子，要么是它的左孩子（没有右孩子的时候),所以只要用一个指针记录一下 上一个处理的节点就行了。

前序中序后序遍历的递归和非递归遍历的实现

::: {.code-include lexer="cpp"} ./binary-tree-travel.cpp :::