前言
前面讲过，二叉树是具有天然的递归结构的，那么为什么要迭代遍历呢？是不是多此一举？
其实这个问题可以思考一下，递归的好处是什么，坏处又是什么？
对我个人而言
优势：代码优雅，可读性强。
劣势：空间复杂度高
那么迭代能解决啥问题内？
首先要清楚的是递归的空间复杂度是怎么产生的，因为调用栈的增多，每次递归调用自身都会开辟一个新的栈空间，所以空间复杂度为O(n)。如果采用迭代的形式，可以避免的是调用栈的空间，通过增加多个指针，建立遍历的前后节点关联关系，就可以做到将空间复杂度降为O(1)，这就是Morris遍历了。
Morris遍历也是一种迭代遍历二叉树的方式，今天我们先从基本的迭代入手，作为Morris的前奏~
我之前再刷leecode的时候注意到有些时候题目会拓展让你思考："能否用迭代形式完成本题？"，可能也是我对递归爱得深沉，很多时候我要憋好久才能从递归这个思路转化为迭代的思路，但是时间久了，发现这样每次都耗时好久转化思路也不是个办法，就想着找一个通用的方法论，能不能迅速帮助自己完成这件事。
首先先分析递归和迭代的不同。
递归的判断是要找到终点，迭代也是一样，迭代的本质是到达最后一个元素就停下来，这个最后一个元素就是终点。
此外，递归每次的调用自身都会有一个开辟一个新的栈空间，但是迭代没有，所以整理下关键点。
递归的终点是子问题的终点，迭代的终点是最后一个元素。
递归是天然消耗调用栈空间的，迭代没有额外的空间。
接下来我们要做的事情，就是用迭代的方式模拟递归的调用，也就是用迭代的方式吧递归的调用给表达出来。这里，我们先尝试处理一下二叉树的前序遍历。
public void traversal(TreeNode node) {
if(node == null) {
return;
}
// 前序遍历
System.out.println(node.val);
traversal(node.left);
traversal(node.right);
}
上面是二叉树的前序遍历，我们的迭代遍历就从模拟递归开始，
1、构造一个栈，来模拟递归的调用栈。
2、确定迭代的条件。
观察递归的遍历可得，两种形式会让当前栈的递归调用停止
1、node==null
2、当前栈的调用栈为空。
那么以此，我们先把迭代的模板写出来
public void traversal(TreeNode node) {
Stack<TreeNode> stack = new Stack<>();
/**
* node与栈不同时为空,迭代就继续进行
*/
while (node != null || !stack.empty()) {
}
}
接下来前序遍历的路径，简单来说就是:
记录当前节点->往左走，走一步记录一步->走不动了，回退一个->往右走一步->记录当前节点->往左走，走一步记录一步->走不动了，回退一个......
如此循环，所以根据这个思路，我们吧步骤拆分一下
1、记录当前节点（压栈）
2、往左走，走一步记录一步（不断移动指针到左子树,并压栈）
3、走不动了，回退一个（出栈）
4、往右走一步（移动指针到右子树）
然后，看代码
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
// 辅助栈
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
// 当前node与栈不同时为空就继续迭代
while (!stack.isEmpty() || node != null) {
// 前序遍历，当前节点不为空，记录当前节点，并压栈
if (node!=null) {
res.add(node.val);
stack.add(node);
}
// 一直往左走，走一步，压一次栈，知道走不动
while (node != null && node.left!=null) {
node = node.left;
res.add(node.val);
stack.push(node);
}
// 回退一步
node = stack.pop();
// 往右走一步
node = node.right;
}
return res;
}
同理，分析一下中序遍历，中序遍历的路径，就是
把当前节点压栈->往左走，走一步压一次栈>走不动了，回退一个->记录当前节点->往右走一步->把当前节点压栈->往左走，走一步压一次栈->走不动了，回退一个......
继续拆分一下步骤
0、把当前节点压栈
1、往左走，走一步压一次栈（不断移动指针到左子树,并压栈）
2、走不动了，回退一个（出栈）
3、记录当前节点
4、往右走一步（移动指针到右子树）
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
// 辅助栈
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
// 当前node与栈不同时为空就继续迭代
while (!stack.isEmpty() || node != null) {
// 把当前节点压栈
if(node !=null) {
stack.push(node);
}
// 一直往左走，走一步，压一次栈，直到走不动
while (node != null && node.left!=null) {
node = node.left;
stack.push(node);
}
// 回退一步
node = stack.pop();
//记录当前节点
res.add(node.val);
// 往右走一步
node = node.right;
}
return res;
}
最后是后序遍历，这个稍微复杂点，但是也不怕，还是先分析一下后序的调用路径。
压入当前节点->往左走，走一步压一次栈->走不动了，回退一个->往右走一步
到这里的路径和前序中序很相似，区别在于往右走这一步的点，此时有两种情况
1、节点为空，弹栈，记录节点。
2、节点有值，继续向左走
这里可以注意到，在后序遍历中，有两次弹栈，一次是向左走走到头的的弹栈，一次是往右走到空节点的弹栈，然而只有从右节点的弹栈才可以记录节点信息，基于此，我们需要一个额外的指针，来判断当前是否是右节点回退的弹栈，代码如下
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
// 辅助栈
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
TreeNode prev = null;
// 当前node与栈不同时为空就继续迭代
while (!stack.isEmpty() || node != null) {
// 把当前节点压栈
if (node != null) {
stack.push(node);
}
// 一直往左走，走一步，压一次栈，直到走不动
while (node != null && node.left != null) {
node = node.left;
stack.push(node);
}
// 回退一步
node = stack.pop();
// 判断右节点是否为空 || 判断是否是右节点回退
if (node.right == null || node.right == prev) {
// 记录当前节点
res.add(node.val);
// 记录当前节点,为了判断下次回退是否是右节点回退
prev = node;
//因为执行到这里,当前的node左右子树都已经遍历完成,将node置为空,下一次进入循环直接继续弹栈
node = null;
} else {
// 右节点不为空,且是从左节点回退,右子树还未遍历,往右走一步,并将当前节点压栈
stack.push(node);
node = node.right;
}
}
return res;
}
到这里，迭代的前中后序遍历也梳理完成，代码的写法上主要是为了模拟递归的调用，还有可以优化的空间，不过这样的一种思路，可以便与以后将其他的递归调用转化为迭代。
在写完写篇文章之后，我们可以进行空间复杂度为O(1)的Morris遍历了。
网友评论