算法通过村第七关-树(递归/二叉树遍历)黄金笔记|迭代遍历

---

前言

---

提示：在一个信息爆炸却多半无用的世界，清晰的见解就成了一种力量。 --尤瓦尔·赫拉利《今日简史》

你是不是觉得上一关特别简单，代码少，背下来就行了，但是如果你要真的理解透了，尝试一下这个一关的练习，用迭代的方式在展示一下，我们就看看非递归方式实现过程。

当然在面试的时候，如果你靠二叉树的前中后序遍历，面试官很可能不让你使用递归方式，因为太简单，可能会点名要你采用迭代的方式，所以这种方式也是必要掌握的。

理论上，递归可以解决的事情都可以通过迭代的方式解决，但是会很复杂，上面的几个递归遍历方法，背下来但是面试的时候不要求使用你就很难受的。

递归就是每次执行方法调用都会先把当前的局部变量、参数值和返回地址等压入栈中，后面再递归返回的时候，从栈顶弹出上一层的各项参数继续执行，这就是递归为什么自动返回并执行上一层方法的原因。我们这里采用迭代方法练习这三道题：

推荐题目⭐⭐⭐⭐：

144. 二叉树的前序遍历 - 力扣（LeetCode）

94. 二叉树的中序遍历 - 力扣（LeetCode）

145. 二叉树的后序遍历 - 力扣（LeetCode）

1. 迭代法实现前序遍历

前序遍历是中左右，如果还有子树就是一直向下找。完了之后再返回从最底层逐步向上向右找。不难写出代码，但是要主以空节点不如栈。

/*** 二叉树的前序遍历* @param root* @return*/public static List<Integer> preOrderTraversal(TreeNode root) {// 校验参数if (root == null){return new ArrayList<Integer>();}// 创建空间List<Integer> res = new ArrayList<Integer>();Deque<TreeNode> stack = new LinkedList<>();// 保留根节点TreeNode node = root;// 只要根节点不空或者栈不空 就循环遍历while(!stack.isEmpty() || node != null){// 中左右while(node != null){res.add(node.val);stack.push(node);node = node.left;}node = stack.pop();node = node.right;}return res;}

2. 迭代法实现中序遍历

再来看看中序遍历，中序遍历时左中右，先访问的时二叉树的左子树，然后再一层一层向下访问，知道达到树的最左底部，在处理节点（也就是把节点数值放入res列表）。在使用迭代法写中序遍历，就需要借助指针的遍历帮助访问节点，栈则用来处理节点上的元素。

看下代码实现：

    /*** 二叉树中序遍历* @param root* @return*/public static List<Integer> inorderTraversal (TreeNode root) {// 参数检验if (root == null){return new ArrayList<Integer>();}// 创建空间List<Integer> res = new ArrayList<Integer>();// 栈存储引用Deque<TreeNode> stack = new LinkedList<>();// 根节点不为空或者栈不为空 一直向下遍历while (root != null ||!stack.isEmpty() ) {while(root != null){stack.push(root);root = root.left;}root = stack.pop();res.add(root.val);root = root.right;}return res;}

3. 迭代法实现后序遍历

后续遍历的非递归方法有三种基本实现思路

1. 反转法
2. 访问标记法
3. Morris法

说是话这三种方法理解起来都有些难度，如果你想挑战一下你的头发，我觉得你可以试一试。

个人觉得访问标记法时最难理解的方法，Morris法时国外的大佬发明的巧思：不是用栈，而使用树中大量的空闲指针完成的，但是实现起来也是很麻烦。感兴趣的同学可以参考这篇文章看下：

【递归+迭代详解】二叉树的morris遍历、层序遍历、前序遍历、中序遍历、后序遍历_morris 递归_威斯布鲁克.猩猩的博客-CSDN博客

这里你们估计已经猜到我们要使用那种方法了：反转发。

我们看下图：

我们可以看到后序遍历的结果是seq = {9 5 7 4 3 }，我们将其反转后的结果是 new_seq = {3 4 7 5 9}.

你有没有发现有什么不一样的地方，看new_seq的序列是不是和前序的思路几乎一致，只不过是左右反了，前序是先中间然后再左右，这里变成了先中间然后再右左。我们完全可以改造一下前序遍历的思路，得到序列new_seq之后，然后再将结果反转过来就是我们想要的结果了。

这真是个天才🤔：

 	/*** 反转法实现** @param root* @return*/public static List<Integer> postOrderTraversal(TreeNode root) {// 参数校验if (root == null) {return new ArrayList<Integer>();}// 创建空间List<Integer> res = new ArrayList<Integer>();Deque<TreeNode> stack = new LinkedList<TreeNode>();// 保留根节点信息TreeNode node = root;// 根节点不为空或者栈不为空，不断遍历下去while (!stack.isEmpty() || node != null) {while (node != null) {res.add(node.val);stack.push(node);node = node.right;}node = stack.pop();node = node.left;}// 重新反转分到结果集Collections.reverse(res);return res;}

这个方法可以巧妙的避开后序遍历的坑，感兴趣的同学可以从后续慢慢写，研究下他的妙处。

---

总结

提示：二叉树的迭代遍历；栈的思想；反转法