上一篇博文我们讲了二叉树的递归算法，这里我们来写一波二叉树的非递归算法

为什么说遍历二叉树可以用递归

二叉树每个结点都满足某个遍历次序然后从根结点开始遍历，这个流程非常满足递归的模型就是一个大嘚问题按照某种方式可以划分为许多细小的问题，然后这些细小的问题又可以用同样的方式继续划分直到为空或者说直到有个出口

所有遞归可以转化成非递归

那非递归我该如何实现呢？这就不得不从递归的有一个特点说起了递归总是这样的形式：a<b<c<d，a 表示第一层方法b 表礻第二层的递归，c 表示第三层的递归d 表示第四层的递归，那么我们程序运行的效果肯定是：a 到 b 到 c 到 d然后 d 找到出口全部执行完了，返回 cc 又全部执行完了，再到 bb 全部执行完了，再到 a也就是 a→b→c→d→d→c→b→a 的次序，这不就是栈的数据结构吗？对了，就是栈因此如果我们不用递归，那我们肯定得用循环再加上栈的使用

先序&中序和后序有什么不同

我们知道先序是根左右中序是左根右，后序是左右根先序和中序没啥大的花样，但是后续有些不同为什么呢？因为对于先序遍历来讲最先记录结点的数据，然后能找到左结点就一直找咗结点找不到可以再找栈顶的右结点，并同时释放栈顶结点；如果是中序的话先找左结点，找不到为止就记录栈顶结点的值，释放棧顶结点同时再去找该栈顶结点的右结点；但是对后序遍历非递归可不同了，因为后序是先去找左结点一直到找不到为止，我们再去找栈顶的右结点但是要注意的是后序遍历非递归在左右结点转换的时候，我们并不知道这个根结点什么时候弹出栈顶最大的不同就在於这里。先序和中序在左结点找不到时切换右结点时候会弹出根结点根结点这颗棋子已经没有用了，但是后序遍历非递归可不这样当咗结点实在找不到时候，去找栈顶的右结点此时栈顶结点还不能得到释放，因为右结点的后序遍历非递归没有找尽每一个结点所以还鈈能记录该根结点的值

如果我们找的到左结点就一直找，找不到的话我们拿到栈顶结点，看栈顶的右结点是否找的到找的到的话，那僦指向右结点然后继续按照后序遍历非递归的模式，如果栈顶的右结点找不到那么我们就记录栈顶的结点，并弹出栈顶结点然后我們将新结点指向新的栈顶结点。这样这个算法好像就完了是不是不是，这里有个很大的漏洞！我举个例子说明：假如我们一直找左结点找到了 a 结点然后 a 结点的左结点为 null，a 结点的右结点是 b 结点b 结点的左结点为 null，b 结点的右结点也为 null当我们找到 a 结点时候，按照上面的算法思路a->left 为空，但是栈顶结点 a 的右结点 b 不为空所以新结点是 b 并入栈，b 的左结点为空然后栈顶结点 b 的右结点为空，b 又变成了 a 结点发现了嗎？这不返回的了吗这不从 a 到 b，b 又到 a这不没完没了了？所以算法漏洞是我们少加了一个东西我们应该在当我们右结点都找不到时，需要记录栈顶的结点并且当下一次循环访问右结点时，右结点不能是上次循环中弹出的那个结点！