二叉树统一迭代法解析

引言

?二叉树的遍历无论是通过递归还是迭代都是比较简单的，递归法下不同访问顺序的代码格式较为一致，通过迭代来进行二叉树的前序、中序、后序遍历存在着代码形式不不统一的问题，显得不够优雅。代码随想录里给出了一种适应于这三种顺序遍历的迭代通式，但并没有解释为什么要在其中引入NULL占位，以及其如何发挥作用。本文将针对二叉树统一迭代法给出详细分析。

引入NULL占位原因

简单前序遍历

?首先众所周知，迭代法的最基本思路就是利用栈后进先出的机制来让要遍历的元素始终在栈顶。因此无论是前序遍历还是中序、后续遍历，我们关注的都是节点的入栈顺序。以前序遍历为例，我们会按 中->右->左 的顺序进行入栈操作。而每次出栈时，我们都可以让被遍历完成后的（根）节点立刻弹出，不会留在栈中，栈顶变为下一个子树的根节点。这也是前序遍历简单的原因。以如下的树为例：

前序遍历时栈的变化为为：

• 321->32
• 32->34
• 34->37
• 37->3
• 3->65
• 65->6

中序遍历的不同

?中序遍历的迭代同样应该遵循一样的入栈思路，入栈顺序为遍历顺序右->中->左。此时，问题就出现了，我们需要先遍历到子节点再回到根节点，而如果代码没有针对性解决的而是对根节点和子节点统一处理，将循环：子节点出栈，操作根节点，子节点入栈，操作子节点这四个步骤。以如下二叉树为例：

为了实现右中左的入栈顺序，我们每访问到一个根节点，都要执行pop根节点，push右子节点，push根节点，push左子节点的流程。栈的变化为：

• 654
• 654->65241
• 65241->6524
• 6524->652241

可以看到由于根节点没有弹出，我们从第一个叶子节点返回时会陷入死循环，那么最简单的方案就是告诉算法这里有个访问过q其子树的根节点（通过后缀NULL标识），不让他进入pop根节点，push右子节点，push根节点，push左子节点的流程，直接pop，栈的变化就会变为：

• 654
• 654->652 4NULL 1
• 652 4NULL 1->652 4NULL, OUT1
• 6524->652,OUT4
• 652->650 2NULL 9
• 650 2NULL 9->650 2NULL,OUT9
• 650 2NULL -> 650,OUT2
• 650 ->65,OUT0
• …

因此，实际我们要访问根节点的流程变为了pop根节点，push右子节点，push根节点，打上已访问标记后缀NULL, push左子节点。实际编码过程中，我们则是通过判断当前节点是否为NULL来判断其前一个节点是要进入遍历其子树的流程，还是直接输出。
?同理，只要我们是通过调整入栈顺序来实现某种顺序遍历，都可以放置占位符NULL来区分要在该节点遍历子树还是直接输出，具体的代码可以参见:二叉树的统一迭代法

总结

?二叉树的统一迭代法有两个要点：1.确定入栈顺序；2.放置占位符来区分是否要探索当前根节点的子树。