阿里二面的算法题 非递归写法 前序遍历 void pretOrder(TreeNode *root){ if(root==nullptr) return root; TreeNode...p=p->left; } p=st.top(); st.pop(); p=p->right; } } 中序遍历...} p=st.top(); coutval; st.pop(); p=p->right; } } 后序遍历...*root){ if(root==nullptr) return root; TreeNode *p=root; TreeNode *r=nullptr; //记录最近访问的节点
数据结构二叉树遍历基础，递归解法在很早之前的博客就以C语言的形式总结了，这篇博文聚焦非递归解法。...二叉树的前序、中序、后序遍历都可以借助栈来实现，因为递归本质也是靠栈来实现的，中序遍历还有一种比较难想的镜像法。 前序遍历 leetcode 144....Binary Tree Preorder Traversal 直接使用栈，入栈顺序先右子树在左子树。...Binary Tree Inorder Traversal 维护一个cur指针和栈，cur指针指向当前处理的节点，栈中存将要处理的节点，二者任意为空结束循环。...Binary Tree Postorder Traversal 直接使用栈，入栈顺序先左子树后右子树(跟前序遍历相反，想一想为什么)，逆序加入结果集(想一想为什么)。
路径所包含边的个数为路径的长度； 祖先结点（Ancestor）：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点； 子孙结点（Descendant）：某一结点的子树中的所有结点是这个结点的子孙；...完全二叉树 一棵二叉树至多只有最下面的一层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。...平衡二叉树 它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树 前序、中序、后序 首先给出二叉树节点类： 树节点： class TreeNode { int...(左右根) 先序遍历 递归先序遍历 递归先序遍历很容易理解，先输出节点的值，再递归遍历左右子树。中序和后序的递归类似，改变根节点输出位置即可。...中序和后序也都涉及到回溯，所以都需要用到栈。
二叉树的前序遍历 前序遍历的顺序是根、左、右。任何一颗树都可以认为分为左路节点，左路节点的右子树。先访问左路节点，再来访问左路节点的右子树。...当两个同时为空时，循环结束，最终得到前序遍历。 一个节点出栈说明这个节点及其左子树已经访问完了，因为我们是先把左路节点存入栈中，此时还剩右子树没有访问。...后序的遍历顺序是左、右、根。...、中序遍历、后序遍历的非递归遍历三种方法都是类似的，差别在于访问栈顶的元素的时机不同,访问控制不同。...其中前序和中序大致相同，而后序需要去进行判断栈顶的右子树情况。
前序遍历： struct node { int val; node *left,*right; }; vector preorder(node *root) { vector...p = p->left; } else { auto top = st.top(); st.pop(); p = top->right; } } return res; } 中序遍历...= p->left; } p = st.top(); st.pop(); res.push_back(p->val); p = p->right; } return res; } 后序遍历
，netty，postgresql 这次就来整合下 树的遍历 没什么难的看了一上午，看完发现，真说出来我的理解，也不是你们的理解方式，所以这篇全代码好了。...前序遍历，中序遍历，后序遍历的区别就是根在前（根左右），根在中（左根右），根在后（左右根） 在最后补全所有源码 二 广度优先遍历 层次遍历 //广度优先遍历 层次遍历 public...preOrder(subTree.leftChild); preOrder(subTree.rightChild); } } //前序遍历的非递归实现...= null) { //递归在左子树中搜索 return p; } else { //递归在右子树中搜索...visted(node); node = node.rightChild; } } } //后序遍历的非递归实现
真正理解三种遍历 还记得我们先序和后序遍历时候跑的顺序么？按照这个顺序再跑一次，就是围着树的外围跑一整圈。...先序中序和后序唯一的不同就是，在经过结点的三次中，哪次访问（输出或者打印或者做其他操作）了这个结点。有点像大禹治水三过家门，他会选择一次进去。...先序遍历顾名思义，就是在第一次经过这个结点的时候访问了它。就是从父节点来的这个箭头的时候，访问了它。 中序遍历也和名字一样，就是在第二次经过这个结点的时候访问了它。...其实不管是前序中序还是后序，在程序里跑的时候都是按照同样的顺序跑的，每个结点经过三遍，第几遍访问这个结点了，就叫什么序遍历。...但是知道前序、中序、后序中的中序和前序或后序数组两种也可以还原二叉树，为何可以推出二叉树的数据结构。
树的遍历是指按照某种顺序访问树中的每一个节点。...常见的树的遍历方法有三种：前序遍历（Preorder Traversal）、中序遍历（Inorder Traversal）和后序遍历（Postorder Traversal）。...前序遍历的JavaScript实现 /** * 前序遍历二叉树 * @param {TreeNode} root - 二叉树的根节点 * @param {number[]} result - 存储遍历结果的数组...中序遍历的JavaScript实现 /** * 中序遍历二叉树 * @param {TreeNode} root - 二叉树的根节点 * @param {number[]} result - 存储遍历结果的数组...(root)); // 输出: [2, 3, 1] 四、总结 树的遍历是树操作中的基础内容，通过不同的遍历方法，我们可以以不同的顺序访问树中的节点： 前序遍历：先访问根节点，再访问左子树，最后访问右子树
前言 大家好，我是bigsai，好久不见，甚是想念！ 今天带大家征服二叉树的前中后序遍历，包含递归和非递归方式，学到就是赚到！...前序遍历在二叉树树的顺序可以看下图(红色箭头指向的表示需要访问的，可以看出从父节点枚举下来第一次就要被访问)。 在具体实现的方式上，有递归方式和非递归方式实现。...中序遍历的顺序是左节点，根节点，右节点 ，在前序中先根后左其实是有点覆盖的关系(这个左就是下一个跟)，在其非递归枚举实现上我们访问右节点时候是先抛出父节点不访问，直接访问父节点的右节点，如果抛出父节点访问这个父节点...递归 二叉树递归方式后序遍历很简单，跟前序中序的逻辑一样，在力扣145有后序的code测试大家可以自己尝试一下。...非递归的后序就稍微难一点了，大家可以回顾一下二叉树的前序和中序遍历，其实都是只用一个栈直接抛出就可以找到右节点，抛出后栈就空了，但是这个后序遍历的顺序是 左子树 ---> 右子树 --->根节点，也就是处理完右节点
求有多少个节点 递归：后序，通过递归函数的返回值计算节点数量 迭代：层序遍历 二叉树：是否平衡 递归：后序，注意后序求高度和前序求深度，递归过程判断高度差 迭代：效率很低，不推荐 二叉树：找所有路径 递归...：前序，方便让父节点指向子节点，涉及回溯处理根节点到叶子的所有路径 迭代：一个栈模拟递归，一个栈来存放对应的遍历路径 二叉树：递归中如何隐藏着回溯 详解二叉树：找所有路径中递归如何隐藏着回溯 二叉树：求左叶子之和...（二叉树系列三） 本周小结！（二叉树系列四） 最后总结 「在二叉树题目选择什么遍历顺序是不少同学头疼的事情，我们做了这么多二叉树的题目了，Carl给大家大体分分类」。...涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。 求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。...求二叉搜索树的属性，一定是中序了，要不白瞎了有序性了。 注意在普通二叉树的属性中，我用的是一般为后序，例如单纯求深度就用前序， 二叉树：找所有路径也用了前序，这是为了方便让父节点指向子节点。
后序遍历 代码实现 代码解释 总结 在二叉树的问题中，给定二叉树的前序遍历（Preorder）和中序遍历（Inorder）序列，如何求得其后序遍历（Postorder）序列是一个经典的面试题。...给定前序遍历和中序遍历序列，我们需要构建二叉树并输出其后序遍历序列。 实现思路 重建二叉树：利用前序遍历和中序遍历的特性，通过递归方法重建二叉树。...在中序遍历中找到该根节点的位置，可以将中序遍历数组分为左子树和右子树两部分。递归地对这两部分继续构建左右子树。 2....后序遍历 在构建好的二叉树上进行后序遍历，按左子树 -> 右子树 -> 根节点的顺序输出节点值。...buildTree 方法：接受前序遍历和中序遍历数组，构建并返回二叉树的根节点。 buildTreeHelper 方法：递归地构建二叉树。
确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。...，所以递归函数返回类型就是void，代码如下： void traversal(TreeNode* cur, vector& vec) 确定终止条件：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了...，那么本层递归就要要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下： if (cur == NULL) return; 确定单层递归的逻辑：前序遍历是中左右的循序，所以在单层递归的逻辑..., vec); // 右 单层递归的逻辑就是按照中左右的顺序来处理的，这样二叉树的前序遍历，基本就写完了，在看一下完整代码： 前序遍历： class Solution { public: void...} 此时大家可以做一做leetcode上三道题目，分别是： 144.二叉树的前序遍历 145.二叉树的后序遍历 94.二叉树的中序遍历 可能有同学感觉前后中序遍历的递归太简单了，要打迭代法（非递归），
「确定递归函数的参数和返回值：」确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。...，所以递归函数返回类型就是void，代码如下： void traversal(TreeNode* cur, vector& vec) 「确定终止条件」：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了...，那么本层递归就要要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下： if (cur == NULL) return; 「确定单层递归的逻辑」：前序遍历是中左右的循序，所以在单层递归的逻辑..., vec); // 右 单层递归的逻辑就是按照中左右的顺序来处理的，这样二叉树的前序遍历，基本就写完了，在看一下完整代码： 前序遍历： class Solution { public: void...我是程序员Carl，哈工大师兄，先后在腾讯和百度从事技术研发多年，利用工作之余重刷leetcode。
深入理解前中后序 之前二叉树的文章，总有读者留言说看不出解法应该用前序中序还是后序，其实原因是你对前中后序的理解还不到位，这里我简单解释一下。...但是我想说，前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点，绝不仅仅是三个顺序不同的 List： 前序位置的代码在刚刚进入一个二叉树节点的时候执行； 后序位置的代码在将要离开一个二叉树节点的时候执行...画成图，前中后序三个位置在二叉树上是这样： 你可以发现每个节点都有「唯一」属于自己的前中后序位置，所以我说前中后序遍历是遍历二叉树过程中处理每一个节点的三个特殊时间点。...当时我是用二叉树的最大深度这个问题来举例，重点在于把这两种思路和动态规划和回溯算法进行对比，而本文的重点在于分析这两种思路如何解决二叉树的题目。...接下来主要说下后序位置，和前序位置对比，发现前序位置的代码执行是自顶向下的，而后序位置的代码执行是自底向上的： 这不奇怪，因为本文开头就说了前序位置是刚刚进入节点的时刻，后序位置是即将离开节点的时刻。
遍历方式 二叉树的常见遍历方式如下几种： 前序遍历： 访问根节点，前序遍历方式访问左子树，前序遍历方式访问右子树； 中序遍历： 中序遍历方式访问左子树，访问根节点，中序遍历方式访问右子树； 后序遍历...tips tips： 1.前序和中序的回溯操作，都是访问上一层的右子树，因为无论是根-左-右，或者左-根-右，右子树访问结束后，都表示根节点和左子树已经访问过。...代码中使用栈来保存上一层的节点，即栈中最后一个元素即为上一层的根节点，通过出栈操作来完成回溯。 中序遍历 中序遍历二叉树顺序为左子树-根节点-右子树形式。...与前序和中序遍历不同之处在于，后序遍历在根节点的输出上需要多做一些工作。 BT 分析上图 BT 中的两颗二叉树： 【1】树 bt1 中，二叉树 遍历结束后，输出上一层的根节点 的值。...附录 以上是四种遍历方式的描述和代码示例，下面给出测试和输出。其中树结构 引用自 二叉搜索树 中定义。
本文将重点介绍二叉树的前序、中序和后序遍历，并讨论如何利用这些遍历方式解决一些常见的问题，包括查找两个节点的最近公共祖先和计算两个节点之间的距离。...通过本文的学习，您将深入了解这些核心概念，并获得代码示例来应对实际问题。前序、中序和后序遍历在开始讨论问题解决方案之前，我们需要了解二叉树的三种常见遍历方式：前序遍历、中序遍历和后序遍历。...preorder(node.left) # 递归遍历右子树 preorder(node.right)中序遍历中序遍历同样是一种深度优先遍历方式，但它的顺序是先遍历左子树...# 访问当前节点 visit(node) # 递归遍历右子树 inorder(node.right)后序遍历后序遍历同样是深度优先遍历，它的顺序是先遍历左子树，...解决方案为了解决这个问题，我们可以利用二叉树的性质和遍历方式。首先，我们从根节点开始进行后序遍历。在遍历过程中，我们检查当前节点是否等于其中一个目标节点。
，这里我要提醒各位一下，虽然在代码上表示是单独的左右两个节点，但是正确的理解策略是把这两个节点，分别看成是一棵树，也即左子树和右子树，理解这一点至关重要，因为这是一个嵌套的定义，每个左，右子节点下面都可能还有无数个类似于这个节点本身的结构...递归虽然可以写出非常简洁的代码，但是想要理解和看清递归的本质可不是一件容易事。 在二叉树的深度遍历的三种遍历策略里面，有一个共性，那就是无论哪种策略，都是先遍历左子树，然后再右子树。...： 1 12 5 6 9（前序） 5 12 6 1 9（中序）5 6 12 9 1（后序） 从上面的能够看到，递归的代码非常简洁，但是如果不明白原理只会看的一头雾水。...为了帮助理解递归的工作方式，我们接着用循环迭代+创建显式的栈容器来实现同样的前，中，后序遍历策略。...，我们就需要优先继续拆分这颗子树，直到找到叶子节点，找叶子节点的过程其实就是在递归的压栈，当找到叶子节点之后，就从开始原路返回，这个过程就是出栈，至于前，中，后序的遍历，无非是遍历的顺序的问题，掌握这一点
可能很多读者朋友对前序遍历这个名字是感到有点陌生的，前序遍历其实就是访问根结点的顺序在左右子树之前，也就是说我们是先访问根结点的数据，然后在取访问根结点的左右孩子，从而我们可以知道前序遍历的遍历顺序是根结点... 中序遍历通过它的名字我们就可以知道，根结点是在左子树和右子树之间进行访问的，所以从这我们就可以知道，前中后序遍历，其实是通过访问根结点的顺序来进行区分的，所以中序遍历的访问顺序是：左子树 ——根结点...2.2.2.中序遍历的代码实现 此时我们肯定也是用到了函数递归，第一步，我们依旧是确定递归的条件，此时递归的条件和前序遍历是一样的，我们仍需判断此时递归传过来的结点是不是空的结点，如果是空的结点，我们直接返回结束函数就好...，之后我们打印的顺序自然是不能放在开头了，我们先递归左子树，然后打印结点的数据，之后在递归右子树，此时我们的函数也是写完了，与我们写前序遍历的函数是类似的，只不过此时打印的位置往后走了一下而已，下面小编给出代码图...，访问根结点的操作是放在了左右子树之后了，所以后序遍历的遍历顺序是：左子树——右子树——根结点（俗称左右根），我们先访问左子树的值，然后访问右子树的值，最后在访问根结点的值，在知道了前序遍历和中序遍历以后
遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础 按照规则，二叉树的遍历有： 前序 / 中序 / 后序的递归结构遍历 ： 1....我们可以用递归来解决 假如，传入函数的节点是空那就直接返回，若不为空，打印当前数值，把对应的左孩子与右孩子分别传进去，子节点与其父亲节点处理问题思路相同，符合把大事化小原则，是递归思想，那前中后序代码，...其实就是打印与递归顺序不同，前序就是先打印再递归左孩子，最后递归右孩子，而中序就是先递归左孩子，再打印，再递归右孩子，后序就是先递归左孩子，再递归右孩子，最后打印 代码如下 void BinaryTreePrevOrder...K行节点个数，不返回最后一行叶子结点个数，返回任意一行节点个数 假如我返回第三行的节点个数，那在我们遍历过程中，我们如何确定节点是否是第三行那，我们有图可以过一行K减一，只要向下递归一行K减一，到目标行第三行...5.寻找x节点 这个首先通过先序遍历遍历每个节点，找到的话返回这个节点，若没找到，返回NULL，扎到的话用临时变量接收，不能直接返回，以为在递归遍历中，你返回返回的是递归过程中上一个函数，并不能完全返回出来
，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，「因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。」...那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了「处理顺序和访问顺序是不一致的...） 再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图： ?...// 将结果反转之后就是左右中的顺序了 return result; } }; 总结 此时我们用迭代法写出了二叉树的前后中序遍历，大家可以看出前序和中序是完全两种代码风格，并不想递归写法那样代码稍做调整...我是程序员Carl，哈工大师兄，先后在腾讯和百度从事技术研发多年，利用工作之余重刷leetcode。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
腾讯会议
云直播
对象存储
