收录网站的平台有哪些,网易企业邮箱登入入口,网站设计怎么弄,辽宁工程招标网信息平台文章目录 前言1. 迭代法实现前序遍历2. 迭代法实现中序遍历3. 迭代法实现后序遍历总结 前言 提示#xff1a;在一个信息爆炸却多半无用的世界#xff0c;清晰的见解就成了一种力量。 --尤瓦尔赫拉利《今日简史》 你是不是觉得上一关特别简单#xff0c;代码少#xff0c;背… 文章目录 前言1. 迭代法实现前序遍历2. 迭代法实现中序遍历3. 迭代法实现后序遍历总结 前言 提示在一个信息爆炸却多半无用的世界清晰的见解就成了一种力量。 --尤瓦尔·赫拉利《今日简史》 你是不是觉得上一关特别简单代码少背下来就行了但是如果你要真的理解透了尝试一下这个一关的练习用迭代的方式在展示一下我们就看看非递归方式实现过程。 当然在面试的时候如果你靠二叉树的前中后序遍历面试官很可能不让你使用递归方式因为太简单可能会点名要你采用迭代的方式所以这种方式也是必要掌握的。 理论上递归可以解决的事情都可以通过迭代的方式解决但是会很复杂上面的几个递归遍历方法背下来但是面试的时候不要求使用你就很难受的。
递归就是每次执行方法调用都会先把当前的局部变量、参数值和返回地址等压入栈中后面再递归返回的时候从栈顶弹出上一层的各项参数继续执行这就是递归为什么自动返回并执行上一层方法的原因。我们这里采用迭代方法练习这三道题
推荐题目⭐⭐⭐⭐
144. 二叉树的前序遍历 - 力扣LeetCode
94. 二叉树的中序遍历 - 力扣LeetCode
145. 二叉树的后序遍历 - 力扣LeetCode
1. 迭代法实现前序遍历
前序遍历是中左右如果还有子树就是一直向下找。完了之后再返回从最底层逐步向上向右找。不难写出代码但是要主以空节点不如栈。
/*** 二叉树的前序遍历* param root* return*/public static ListInteger preOrderTraversal(TreeNode root) {// 校验参数if (root null){return new ArrayListInteger();}// 创建空间ListInteger res new ArrayListInteger();DequeTreeNode 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 ListInteger inorderTraversal (TreeNode root) {// 参数检验if (root null){return new ArrayListInteger();}// 创建空间ListInteger res new ArrayListInteger();// 栈存储引用DequeTreeNode 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. 迭代法实现后序遍历
后续遍历的非递归方法有三种基本实现思路
反转法访问标记法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 ListInteger postOrderTraversal(TreeNode root) {// 参数校验if (root null) {return new ArrayListInteger();}// 创建空间ListInteger res new ArrayListInteger();DequeTreeNode stack new LinkedListTreeNode();// 保留根节点信息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;}这个方法可以巧妙的避开后序遍历的坑感兴趣的同学可以从后续慢慢写研究下他的妙处。 总结
提示二叉树的迭代遍历栈的思想反转法
