有没有办法通过使用索引来迭代/递归二叉树？ - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

关于二叉树，你该了解这些！

那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：深度优先遍历前序遍历（递归法，迭代法）中序遍历（递归法，迭代法）后序遍历（递归法，迭代法）广度优先遍历层次遍历（迭代法）在深度优先遍历中...最后再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。...「之前我们讲栈与队列的时候，就说过栈其实就是递归的一种是实现结构」，也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。...「说道二叉树，就不得不说递归，很多同学对递归都是又熟悉又陌生，递归的代码一般很简短，但每次都是一看就会，一写就废。」「那么请跟住Carl的节奏，不仅彻底掌握二叉树的递归遍历，还有迭代遍历！」...栈与队列：滑动窗口里求最大值引出一个重要数据结构栈与队列：有没有想过计算机是如何处理表达式的？

7068 5

二叉树非递归版的后序遍历算法

树的递归遍历算法很容易理解，代码也很精简，但是如果想要从本质上理解二叉树常用的三种遍历方法，还得要思考树的非递归遍历算法。...读完后的收获： “”将学到二叉树的后序遍历的非递归版本明白栈这种数据结构该怎么使用 02—讨论的问题是什么？...主要讨论二叉树的非递归版后序遍历该如何实现，包括借助什么样的数据结构，迭代的构思过程等。...需要用到一个指针存储着上一迭代的访问过的节点。以上就是后序遍历非递归版的思路。 05—实现代码这里我们以二叉树为例，讨论二叉树的后序遍历的非递归版实现。...06—总结讨论了二叉树的非递归版后序遍历算法，算法借助栈，相比于前序遍历和中序遍历，它多了一个指针指向上一迭代中访问过的节点，目的是为了判断是否向右子树展开，算法的时间和空间复杂度都为 O(n)。

1.2K10 0

您找到你想要的搜索结果了吗？

是的

没有找到

二叉树的中序遍历

二叉树的中序遍历力扣题目链接[1] 给定一个二叉树的根节点 root ，返回它的「中序」遍历。...，你可以通过迭代算法完成吗？...思路：与前序遍历类似，我们先使用递归求解，再来使用迭代求解。递归递归方式整体思路都是类似的，唯一不同的地方在于将节点放入结果数组的时机。需要跟前中后的顺序对应起来。...因此我们要想办法先找到最左侧的子节点。这里依旧使用栈来实现。我们需要朝着左侧方向一条道走到黑，直到左子节点没有左子节点为止。寻找左子节点的途中，将经过的节点放入栈中。...递归的思路很好理解，这里需要重点掌握迭代的方式。

1543 0

二叉树八股文：递归改迭代通用模板

前文 BFS 算法框架详解是利用队列迭代地遍历二叉树，不过使用的是层级遍历，没有递归遍历中的前中后序之分。由于现在面试越来越卷，很多读者在后台问我如何将前中后序的递归框架改写成迭代形式。...而我想要的是一个万能的模板，可以把一切二叉树递归算法都改成迭代。...理论上，所有递归算法都可以利用栈改成迭代的形式，因为计算机本质上就是借助栈来迭代地执行递归函数的。所以本文就来利用「栈」模拟函数递归的过程，总结一套二叉树通用迭代遍历框架。...迭代代码框架想在迭代代码中体现前中后序遍历，关键点在哪里？当我从栈中拿出一个节点p，我应该想办法搞清楚这个节点p左右子树的遍历情况。...迭代解法到这里就搞定了，不过我还是想强调，除了 BFS 层级遍历之外，二叉树的题目还是用递归的方式来做，因为递归是最符合二叉树结构特点的。

4223 0

我的刷题经验总结

比如前文最大子数组问题面对的问题就没办法用滑动窗口，因为数组中的元素存在负数，扩大或缩小窗口并不能保证窗口中的元素之和就会随着增大和减小，所以无法使用滑动窗口技巧，只能用动态规划技巧穷举了。...二叉树系列算法老读者都知道，二叉树的重要性我之前说了无数次，因为二叉树模型几乎是所有高级算法的基础，尤其是那么多人说对递归的理解不到位，更应该好好刷二叉树相关题目。...我之前说过，二叉树题目的递归解法可以分两类思路，第一类是遍历一遍二叉树得出答案，第二类是通过分解问题计算出答案，这两类思路分别对应着回溯算法核心框架和动态规划核心框架。...什么叫通过遍历一遍二叉树得出答案？...-1 : res; } 这个暴力解法加个memo备忘录就是自顶向下的动态规划解法，你对照二叉树最大深度的解法代码，有没有发现很像？

7815 1

【数据结构与算法】二叉树的 4 种遍历

而在遍历左右子树时，仍然按照先访问根节点，然后遍历左子树，最后遍历右子树的方式，直到二叉树为空则返回！遍历的方式又主要分为递归和迭代的方式，其具体实现如下所示。...而在遍历左右子树时，仍然按照先遍历左子树，然后访问根节点，最后遍历右子树的方式，直到二叉树为空则返回！遍历的方式又主要分为递归和迭代的方式，其具体实现如下所示。...遍历的方式又主要分为递归和迭代的方式，其具体实现如下所示。...stack.push(current); current = current.left; }else{ //看最左结点有没有右子树...遍历的方式又主要分为递归和迭代的方式，其具体实现如下所示。

2301 0

JavaScript 实现二叉搜索树

2 初始化二叉树这里实现二叉树的方式是使用 ES6 中的 class 类以及立即执行函数的方式实现： // 立即执行函数在最后会返回出 Tree 这个构造类， // 并赋给外面的变量 const Tree...rootNode) 时就会执行 return 语句，这是递归的出口。在这个程序里，递归想要走出来，就会一直迭代到叶子节点才肯罢休（因为叶子节点的 rootNode.leftNode==null）。...比如上面图片的二叉树，中序遍历的结果是（在二叉搜索树中，中序遍历是从小到大进行排列的）： ? 通过观察二叉树会发现，“6”的前驱和后继全是叶子节点。交换和删除都比较好操作。这难道是巧合吗？...在外部的 remove 函数中使用了大量的递归算法以及条件判断。之所以要重构 root ，很大一部分原因出在这一句： if(!rootNode.leftNode && !...除了之上的办法，还有一种比较直观的办法，这种办法重构的是一部结点。我们在前面已经实现了一个 init(array) 函数，这个函数接收一个数组，这个数组会遍历每个元素然后插入到树中。

3821 0

关于二叉树，你该了解这些......

顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在散落在各个地址的节点串联一起。链式存储如图： ? 链式存储是大家很熟悉的一种方式，那么我们来看看如何顺序存储呢？...那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：深度优先遍历前序遍历（递归法，迭代法）中序遍历（递归法，迭代法）后序遍历（递归法，迭代法）广度优先遍历层次遍历（迭代法）在深度优先遍历中...看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式前序遍历：中左右中序遍历：左中右后序遍历：左右中大家可以对着如下图，看看自己理解的前后中序有没有问题。 ?...最后再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。...之前我们讲栈与队列的时候，就说过栈其实就是递归的一种是实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。

4474 0

一文横扫二叉树的所有遍历方法

多看几遍，我相信你对二叉树的先序遍历会有一定的概念，不急，等我们看完代码，我想你会完全理解的。对于二叉树的先序遍历，我们一般可以采用两种方式：递归和迭代。...，而且存在大量冗余，景禹就不给大家演示了，而且在面试的时候，建议在给面试官给出递归的解法之后，能够再使用迭代进行解答。...接着我们一起来看一下后序遍历的三种实现方式：递归、迭代和取巧！二叉树后序遍历的递归实现相当简单，只需要将前序遍历中res.add(root.val)移动到两个if语句之后即可。...，我们依旧可以使用递归的方式进行解决，注意递归函数helper增加了一个记录当前处理节点的层数： class Solution { List> res = new ArrayList...对于每一种遍历方式都可以使用递归的方式进行实现，其中前中后序还可以借助栈进行迭代实现，而层序遍历可以借助队列进行迭代实现。

6313 0

二叉树：总结篇！（需要掌握的二叉树技能都在这里了）

在每一道二叉树的题目中，我都使用了「递归三部曲」来分析题目，相信大家以后看到二叉树，看到递归，都会想：返回值、参数是什么？终止条件是什么？单层逻辑是什么？...：二叉树的种类、存储方式、遍历方式、定义方式二叉树的遍历方式深度优先遍历二叉树：前中后序递归法：递归三部曲初次亮相二叉树：前中后序迭代法（一）：通过栈模拟递归二叉树：前中后序迭代法（二）统一风格...广度优先遍历二叉树的层序遍历：通过队列模拟求二叉树的属性二叉树：是否对称递归：后序，比较的是根节点的左子树与右子树是不是相互翻转迭代：使用队列/栈将两个节点顺序放入容器中进行比较二叉树：求最大深度...求有多少个节点递归：后序，通过递归函数的返回值计算节点数量迭代：层序遍历二叉树：是否平衡递归：后序，注意后序求高度和前序求深度，递归过程判断高度差迭代：效率很低，不推荐二叉树：找所有路径递归...迭代：比较复杂，意义不大构造最大的二叉树递归：前序，分割点为数组最大值，分左右区间构造迭代：比较复杂，意义不大合并两个二叉树递归：前序，同时操作两个树的节点，注意合并的规则迭代：使用队列，

8364 1

LeetCode - 翻转二叉树

原题备注: 这个问题是受到 Max Howell 的原问题启发的：谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。...解题思路：我想应该有两种办法，第一种是递归...，也是第一反应，第二种就是迭代。...递归法：先进行递归结束的条件判断。然后分别对左右子树进行递归，然后将左右子树互换位置即可。...迭代法：类似深度优先搜索的方式，采用队列存储未访问过的节点，分别将左右子树的节点进行位置互换，然后将节点的子节点存入队列。然后从队列中取出未访问的节点，进行翻转。

4746 0

LeetCode通关：连刷三十九道二叉树，刷疯了！

我们来看一个图例：具体的算法实现主要有两种方式：递归：树本身就是一种带着递归性质的数据结构，使用递归来实现深度优先遍历还是非常方便的。迭代：迭代需要借助其它的数据结构，例如栈来实现。...递归的过程是不断往左边走，当递归终止的时候，就添加节点。现在使用迭代，我们需要自己来用一个数据结构存储节点。那么用什么数据结构比较合适呢？我们自然而然地想到——栈。...我们在前面已经使用迭代法完成了二叉树的深度优先遍历，现在我们来磕一下广度优先遍历。在迭代法深度优先遍历里，我们用了栈这种数据结构来存储节点，那么层序遍历这种一层一层遍历的逻辑，适合什么数据结构呢？...一个以此数组直接递归构建的最大二叉树定义如下：二叉树的根是数组 nums 中的最大元素。左子树是通过数组中最大值左边部分递归构造出的最大二叉树。...右子树是通过数组中最大值右边部分递归构造出的最大二叉树。返回有给定数组 nums 构建的最大二叉树。

8462 0

【刷题】 Leetcode 1022.从根到叶的二进制数之和

难点就在于如何进行每个节点的储存计算，一般来说二叉树都会使用遍历或栈来进行运算。那就让我们来看看这个题如何完美解答吧！！！...，是因为使用位操作效率更高！...思路二（栈迭代巧解版）该算法是使用栈来模拟函数递归的过程： typedef struct TreeNode Node; int sumRootToLeaf(struct TreeNode* root...}else{ root = root->right; } } free(stack); return ret; } 选择遍历二叉树的办法是...这种方法比较复杂，是非递归遍历二叉树的常用方法。总结通过这道题，我学会了递归的深度搜索方法，快速解决问题也初步认识到了非递归遍历二叉树的方法。但还是不太理解，不知道是如何推出来的。

761 0

【算法】二叉树遍历算法总结：前序中序后序遍历

在递归方法下，前中后序遍历都是一个思路，理解起来也比较容易。但是只是用迭代的话，二叉树遍历其实是有难度的！...，这也是为什么LeetCode会在这三题题目的下方写出进阶: 递归算法很简单，你可以通过迭代算法完成吗？这句话了。...本文的主要内容如下：题目定义：上篇：二叉树前序、中序、后序遍历下篇：层序遍历、其他遍历相关题型解题思路：递归 + 迭代+ 莫里斯Morris遍历解题代码：Java + Python 注1：本文中的解题思路会尽量的全面...注2：本文中的代码会尽量简单，易懂，并不会去追求极致的写法（比如：在一行内完成，使用各种非正式的库等）。正文二叉树的定义最多有两棵子树的树被称为二叉树 ?...，主要就是两种思路，一种是递归，一种是迭代。

1.7K2 0

Data Structurestackheapheap的实现索引堆tree并查集图 Graph

i堆的实现可以使用类似二叉树做左节点右节点的实现，定义一个类，左子树右子树和数组。但是基于堆的特殊性质，我们可以使用数组实现 ?...所以比较好的方法就是每一个节点分配一个索引，用索引来建堆。 ? 建堆的时候不使用原值，而是用一个索引。交换也就是交换索引了。 ?...__search(node.left, key) pass 一言不合就递归。二叉树的深度优先遍历前序遍历：先访问当前节点，再依次递归访问左右子树。...self.parent[p] = int(self.find(int(self.parent[p]))) return int(self.parent[p]) 通过递归处理...常规实现就是遍历，不按套路出牌，实现一个迭代器来进行迭代处理。

6833 0

【算法】二叉树遍历算法总结：前序中序后序遍历

在递归方法下，前中后序遍历都是一个思路，理解起来也比较容易。但是只是用迭代的话，二叉树遍历其实是有难度的！...，这也是为什么LeetCode会在这三题题目的下方写出进阶: 递归算法很简单，你可以通过迭代算法完成吗？这句话了。...本文的主要内容如下：题目定义：上篇：二叉树前序、中序、后序遍历下篇：层序遍历、其他遍历相关题型解题思路：递归 + 迭代+ 莫里斯Morris遍历解题代码：Java + Python 注1：本文中的解题思路会尽量的全面...，主要就是两种思路，一种是递归，一种是迭代。...总结：从根节点遍历，先放入所有有左孩子的节点直到没有，然后出栈，出栈的时候就将出栈的数字放入结果集，然后看其有没有右孩子，有的话右孩子入栈。

1.2K4 0

LeetCode刷题实战110：平衡二叉树

解题 https://blog.csdn.net/qq_17550379/article/details/82081501 对于这个问题，我们可以非常快的写出递归版本。...如果不是接着递归判断左子树和右子树是不是一棵平衡二叉树。...或者说我们有什么办法在遍历一遍树（求一次height）的过程中就可以得到答案呢？我们希望当左右子树中存在不平衡的时候就可以提前停止。...同样的，对于可以用递归解决的问题，我们都应该思考一下怎么可以通过迭代去解决。那这个问题怎么通过迭代解决呢？...我们可以先通过BFS得到一个list，然后从list的最后一个节点回退到root，并且计算节点的深度差，更新各节点深度。

2731 0

聊聊二叉树的遍历（递归和非递归）

二叉树也是常用的数据结构，通过使用二叉树可以快速的对数据进行排序或者查找，在常用的堆排序算法中，堆的底层实质就是一个模拟的完全二叉树！等等，什么是完全二叉树？二叉树又是什么？有哪几类？...递归版本（先、中、后序）递归版的遍历算法很简单了，我们只需要改变打印次序就好了，也没有什么可讲的！...（先、中、后序）首先我们要清楚，任何算法的递归版本都可以改成非递归版本，因为函数递归调用其实质就是压栈的过程，那么我们完全可以使用堆栈来模拟这个过程！...// 迭代版 void printPreorder2(TreeNode* head){ cout << "Pre Order:" << endl; if (head !...，并将节点压入栈中，只到找到最左边的叶节点，接着弹出（并打印节点），并看其有没右分支，如果没有，栈再弹出一个节点（根节点），看其有没有右分支。

9513 0

【LeetCode - 101】平衡二叉树

翻译给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。...4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \ 2 2 \ \ 3 3 说明: 如果你可以运用递归和迭代两种方法解决这个问题...我们可以用递归和迭代两种方法来实现，写法不同，但是算法核心都一样。对这棵树同时进行优先访问左子树的前序遍历和优先访问右子树的前序遍历，判断当前访问到的两个节点是不是相等。...return helper(p, q); } private boolean helper(TreeNode p, TreeNode q) { // 判断有没有节点为...举几个常见的例子：红黑树：java jdk中的HashMap 就采用了红黑树这种数据结构 B+树：常见的关系型数据库索引都是使用的B+树，如Mysql的Innodb存储引擎等等… …

3872 0

二叉树的所有路径：不止递归，还有回溯

前序遍历以及回溯的过程如图：我们先使用递归的方式，来做前序遍历。要知道递归和回溯就是一家的，本题也需要回溯。...迭代法至于非递归的方式，我们可以依然可以使用前序遍历的迭代方式来模拟遍历路径的过程，对该迭代方式不了解的同学，可以看文章二叉树：听说递归能做的，栈也能做！和二叉树：前中后序迭代方式统一写法。...总结本文我们开始初步涉及到了回溯，很多同学过了这道题目，可能都不知道自己其实使用了回溯，回溯和递归都是相伴相生的。...我在第一版递归代码中，把递归与回溯的细节都充分的展现了出来，大家可以自己感受一下。第二版递归代码对于初学者其实非常不友好，代码看上去简单，但是隐藏细节于无形。最后我依然给出了迭代法。...对于本地充分了解递归与回溯的过程之后，有精力的同学可以在去实现迭代法。

1.4K6 1

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭