抓好门户网站 建设,丽江建设局网站,三亚网上商城,上海cms建站系统目录
1、前言
2、二叉树的非递归遍历
2.1、先序遍历
2.2、中序遍历
2.3、后序遍历 1、前言 学习二叉树的三种非递归遍历前#xff0c;首先来了解一下递归序#xff1a; 递归序就是按照先序遍历的顺序#xff0c;遇到的所有结点按顺序排列#xff0c;重复的结点也必须记…目录
1、前言
2、二叉树的非递归遍历
2.1、先序遍历
2.2、中序遍历
2.3、后序遍历 1、前言 学习二叉树的三种非递归遍历前首先来了解一下递归序 递归序就是按照先序遍历的顺序遇到的所有结点按顺序排列重复的结点也必须记录。 我们可以发现递归序中每个结点都会遇到三次。 这是因为当进入某一结点时对该结点进行第一次操作然后调用其左孩子结点等左孩子结点结束调用时会返回自己此时就可以对自己进行第二次操作然后再调用其右孩子结点等左孩子结点结束调用时又会返回自己此时就可以对自己进行第三次操作因为不管怎样调用完孩子结点后终究会返回到父结点。 直接给出结论 递归序中第一次遇到该节点时打印结点第二次第三次均不做任何操作这就是先序遍历。 递归序中第二次遇到该节点时打印结点第一次第三次均不做任何操作这就是中序遍历。 递归序中第三次遇到该节点时打印结点第一次第二次均不做任何操作这就是后序遍历。 关于递归序详细的讲解可以看我之前写的一篇博客里面有详细讲解这里就不过多赘述
【算法与数据结构】二叉树的三种遍历代码实现上—— 用递归序知识点讲解-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133609612?spm1001.2014.3001.5501
2、二叉树的非递归遍历 任何递归函数都可以改成非递归函数因为递归函数不是什么玄学只是递归时系统帮忙解决了压栈问题。那么不用递归方式的话只要自己手动进行压栈依然可以完成递归能够实现的功能。 有了上面递归序的知识点作为铺垫就可以很好的理解非递归的实现了。 2.1、先序遍历 递归序中第一次遇到该节点时打印结点第二次第三次均不做任何操作这就是先序遍历。 首先使用cur依次将二叉树所有左边界节点入栈并且打印节点。当此时cur走到叶子节点后将栈顶元素出栈并让cur指向出栈元素的右孩子继续进行左边界节点入栈操作。 public ListInteger preorderTraversal(TreeNode root) {ListInteger list new LinkedList();if(root null) {return list;}StackTreeNode stack new Stack();TreeNode cur root;while(cur ! null || !stack.isEmpty()) {if(cur ! null) {stack.push(cur);System.out.print(cur.val ); //第一次遇到时进行打印cur cur.left;} else {cur stack.pop(); //第二次遇到cur cur.right;}}return list;}
2.2、中序遍历 递归序中第二次遇到该节点时打印结点第一次第三次均不做任何操作这就是中序遍历。 首先使用cur依次将二叉树所有左边界节点入栈。当此时cur走到叶子节点后将栈顶元素出栈后并打印此时第二次遇到该元素。然后让cur指向出栈元素的右孩子继续进行左边界节点入栈操作。 public ListInteger inorderTraversal(TreeNode root) {ListInteger list new LinkedList();if(root null) {return list;}StackTreeNode stack new Stack();TreeNode cur root;while(cur ! null || !stack.isEmpty()) {if(cur ! null) {stack.push(cur); //第一次遇到cur cur.left;} else {cur stack.pop();System.out.print(cur.val ); //第二次遇到时进行打印cur cur.right;}}return list;}
2.3、后序遍历 递归序中第三次遇到该节点时打印结点第一次第二次均不做任何操作这就是后序遍历。 首先使用cur依次将二叉树所有左边界节点入栈。当此时cur走到叶子节点后使用peek()查找出栈顶元素top并非出栈后并打印然后判断top节点是否存在右孩子当存在时则让cur指向top节点的右孩子继续进行左边界节点入栈操作。当top不存在右孩子时则将栈顶元素出栈并打印栈顶元素此时第三次遇到该元素。 public ListInteger postorderTraversal(TreeNode root) {ListInteger list new LinkedList();if(root null) {return list;}StackTreeNode stack new Stack();TreeNode cur root;TreeNode prev null;while(cur ! null || !stack.isEmpty()) {if(cur ! null) {stack.push(cur); //第一次遇到cur cur.left;} else {TreeNode top stack.peek(); //第二次遇到if(top.right ! null prev ! top.right) { //当该节点右子树不为空,并且之前没有去过右子树时cur top.right; } else { //该节点右子树为空或者是已经去过一次右子树了top stack.pop();System.out.print(cur.val ); //第三次遇到时进行打印prev top;}}}return list;} 博主推荐
【LeetCode力扣】单调栈解决Next Greater Number下一个更大值问题-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/136030138?spm1001.2014.3001.5501 【数据结构】二叉搜索树的模拟实现-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/135910604?spm1001.2014.3001.5501 【LeetCode力扣】面试题 17.14. 最小K个数top-k问题-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/135737266?spm1001.2014.3001.5501
如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
