有没有可能在不使用递归或堆栈/队列的情况下获得二叉树的高度？

在不使用递归或堆栈/队列的情况下获得二叉树的高度是可能的。可以使用层次遍历（BFS）算法来实现。

层次遍历是一种广度优先搜索（BFS）的方法，它按照树的层级顺序逐层遍历节点。通过迭代地访问每一层的节点，我们可以计算出二叉树的高度。

具体步骤如下：

创建一个队列，并将根节点入队。
初始化高度为0。
进入循环，直到队列为空：
- 获取当前队列的大小，表示当前层级的节点数。
- 遍历当前层级的节点数次：
  - 出队一个节点。
  - 如果该节点有左子节点，将左子节点入队。
  - 如果该节点有右子节点，将右子节点入队。
- 高度加1。

返回高度作为二叉树的高度。

这种方法不使用递归或堆栈，仅使用队列来实现层次遍历，从而得到二叉树的高度。

腾讯云相关产品和产品介绍链接地址：

腾讯云云服务器（CVM）：https://cloud.tencent.com/product/cvm
腾讯云云数据库 MySQL 版：https://cloud.tencent.com/product/cdb_mysql
腾讯云人工智能平台（AI Lab）：https://cloud.tencent.com/product/ai
腾讯云物联网平台（IoT Hub）：https://cloud.tencent.com/product/iothub
腾讯云移动开发平台（MPS）：https://cloud.tencent.com/product/mps
腾讯云对象存储（COS）：https://cloud.tencent.com/product/cos
腾讯云区块链服务（BCS）：https://cloud.tencent.com/product/bcs
腾讯云腾讯会议：https://cloud.tencent.com/product/tc-meeting
腾讯云云游戏引擎（GSE）：https://cloud.tencent.com/product/gse

相关·内容

树

（先序遍历和后序遍历不能确定唯一的二叉树，因为这时候没法区分左子树和右子树）对于完全二叉树，我们可以使用顺序存储来方便的实现。...这个缺点总是无法避免的。实际上，我们经常使用的是链式存储二叉树。下面给出链式存储二叉树的ADT。...（避免了求出二叉树的先序，中序，或者后序序列。）创建过程如下：输入第一个数据，若不为0，则赋值，入队；若为0，则返回空树。若队列不空，则出队一个元素，并创建该节点的左右子树。...可以在不借助堆栈的情况下使用循环语句来完成。所以前序和中序的非递归函数是几乎一致的。都是借助一个堆栈，将左子树入栈，然后弹出转右子树。...但是后序遍历的最后一句并不是“尾递归”，使得无法仅通过一个堆栈就完成。所以后序遍历的非递归版本和上面的看起来有些不一样。

4262 0

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

二叉树也是常用的数据结构，通过使用二叉树可以快速的对数据进行排序或者查找，在常用的堆排序算法中，堆的底层实质就是一个模拟的完全二叉树！等等，什么是完全二叉树？二叉树又是什么？有哪几类？...让我们开始今天的算法课堂～二叉数的概念和分类 二叉树是每个树节点最多有两个子树的一种特殊的树结构，其有一些内在的性质，比如，若二叉树的层次从0开始，则在二叉树的第i层至多有2^i个节点（i>=0）,高度为...k的二叉树最多有2^(k+1)-1个节点（空树的高度为-1）。...，对其进行中序遍历后，会得到一个有序的列表，这是我们经常用到的一种数的结构平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，并且满足二叉搜索树的规则...（先、中、后序）首先我们要清楚，任何算法的递归版本都可以改成非递归版本，因为函数递归调用其实质就是压栈的过程，那么我们完全可以使用堆栈来模拟这个过程！

9433 0

数据结构

它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率高。 Vector 是矢量队列，和ArrayList一样，它也是一个动态数组，由数组实现。...完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树；叶节点只能出现在最下层和次下层...平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。...Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。...简单来说红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。 B-，B+，B*树 B-树（或B树）是一种平衡的多路查找(又称排序)树，在文件系统中有所应用。

5052 0

【数据结构】树与二叉树（八）：二叉树的中序遍历（非递归算法NIO）

二叉树性质引理5.1：二叉树中层数为i的结点至多有 2^i 个，其中 i \geq 0 。引理5.2：高度为k的二叉树中至多有 2^{k+1}-1 个结点，其中 k \geq 0 。...还可以使用迭代的方式来实现遍历算法，使用栈或队列等数据结构来辅助实现。遍历是二叉树中基础而重要的操作，它为其他许多操作提供了基础，如搜索、插入、删除等。...中序遍历非递归 a. 算法NIO b. 算法解读 NIO算法利用了一个辅助堆栈S来模拟递归过程中的函数调用栈。...通过在循环中不断将左子节点入栈，然后处理栈顶节点，并将指针移动到右子节点，实现了中序遍历的非递归算法。创建一个空堆栈S，并将指针p指向树的根节点t。进入循环，只要p不为空，执行以下步骤： a....这个非递归中序遍历算法可以应用于需要遍历二叉树并按照中序顺序访问节点的场景，例如在构建二叉树的线索化结构时，或者需要按照中序顺序遍历二叉搜索树等情况下。 c.

981 0

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

平衡二叉搜索树平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树...最后一棵不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了1。...最后再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。...「之前我们讲栈与队列的时候，就说过栈其实就是递归的一种是实现结构」，也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。...栈与队列：总结篇！栈与队列：求前 K 个高频元素和队列有啥关系？栈与队列：滑动窗口里求最大值引出一个重要数据结构栈与队列：有没有想过计算机是如何处理表达式的？

7058 5

【数据结构】树与二叉树（九）：二叉树的后序遍历（非递归算法NPO）

二叉树性质引理5.1：二叉树中层数为i的结点至多有 2^i 个，其中 i \geq 0 。引理5.2：高度为k的二叉树中至多有 2^{k+1}-1 个结点，其中 k \geq 0 。...还可以使用迭代的方式来实现遍历算法，使用栈或队列等数据结构来辅助实现。遍历是二叉树中基础而重要的操作，它为其他许多操作提供了基础，如搜索、插入、删除等。...中序遍历非递归【数据结构】树与二叉树（八）：二叉树的中序遍历（非递归算法NIO） 5. 后序遍历非递归 a. 算法NPO b....算法解读算法NPO(t)利用了一个辅助堆栈S来遍历二叉树T的所有节点。如果t为空，则直接返回。创建一个空堆栈S，并将根节点t和初始标记0入栈（S <= (t, 0)）。...Node* stack[100]; // 辅助堆栈，用于模拟递归调用栈 int tagStack[100]; // 标记堆栈，用于记录结点的访问状态 int top = -1;

1281 0

【数据结构】C语言实现链式二叉树(附完整运行代码)

一.了解项目功能在本次项目中我们的目标是实现一个链式二叉树: 该链式二叉树使用动态内存分配空间,可以用来存储任意数量的同类型数据....为直观分析链式二叉树中的递归思路,在后续的功能实现部分,我会频繁使用下面这棵树画函数递归展开图,大家可以先熟悉一下这棵二叉树,我们马上就开始实现具体的功能: 1.实现链式二叉树程序菜单菜单部分的逻辑比较简单...实现层序遍历的思路为(借助队列实现): 将根节点入队如果队首结点不为空,将队首结点不为空的孩子入队访问队首元素并将其出队注:因为在之前的文章中我们已经实现过链队列程序了,所以在树部分我们不涉及讲解链队列的实现...0 : TreeSize(root->left) + TreeSize(root->right) + 1; //从这条语句里体会分治的思想 } 14.实现链式二叉树高度计算 二叉树的高度计算上我们同样采用递归分治的思想...,即 二叉树的高度为左子树和右子树高的那个高度再加上根结点自己的高度,即 二叉树的高度=左子树的高度>右子树的高度?

1351 0

【数据结构】树与二叉树（十）：二叉树的先序遍历（非递归算法NPO）

二叉树性质引理5.1：二叉树中层数为i的结点至多有 2^i 个，其中 i \geq 0 。引理5.2：高度为k的二叉树中至多有 2^{k+1}-1 个结点，其中 k \geq 0 。...还可以使用迭代的方式来实现遍历算法，使用栈或队列等数据结构来辅助实现。遍历是二叉树中基础而重要的操作，它为其他许多操作提供了基础，如搜索、插入、删除等。...中序遍历非递归【数据结构】树与二叉树（八）：二叉树的中序遍历（非递归算法NIO） 5. 后序遍历非递归【数据结构】树与二叉树（九）：二叉树的后序遍历（非递归算法NPO） 6....算法解读算法NPO(t)利用了一个辅助堆栈S来遍历二叉树T的所有节点。如果根节点t为空，则直接返回。创建一个空堆栈S，并将根节点t和初始标记0入栈（S <= (t, 0)）。...如果标记i为2，则表示节点p的左右子树都已处理完毕，将节点p从堆栈S中弹出（S.pop()）。跳转到步骤3，继续循环，直到堆栈S为空。 c. 复杂度分析设二叉树有n个结点。

1061 0

这些题都不会，面试你怎么可能过？

有没有想过它是如何工作的？其思路就是，按照最后的状态排列在先的顺序将工作的先前状态（限于特定数字）存储在内存中。这只用数组是无法实现的，因此堆栈就有了用武之地。可以把堆栈看作一堆垂直排列的书籍。...使用堆栈计算后缀表达式对堆栈中的值进行排序检查表达式中的括号是否平衡队列与堆栈类似，队列是另一种线性数据结构，以顺序方式存储元素。...常问的队列面试问题：使用队列来实现堆栈颠倒队列中前 k 个元素的顺序使用队列生成从 1 到 n 的二进制数链表链表是另一个重要的线性数据结构，刚一看可能看起来像数组，但在内存分配，内部结构以及如何执行插入和删除的基本操作方面有所不同...链表就像一个节点链，其中每个节点包含数据和指向链中后续节点的指针等信息。有一个头指针，指向链表的第一个元素，如果列表是空的，那么它只指向 null 或不指向任何内容。...常问的树面试问题：找到一个二叉树的高度找到一个二叉搜索树中第 k 个最大值找到距离根部“k”个距离的节点找到一个二叉树中给定节点的祖先（ancestors）字典树字典树，也叫“前缀树”，是一种树形结构

1.1K2 0

数据结构：树与二叉树

在递归遍历中，递归工作栈的栈深度恰好为树的深度，最坏的情况下二叉树是有n个结点且递归深度为n的单支树，遍历算法的空间复杂度为O(n)；最好的情况下二叉树达到平衡状态，此时空间复杂度为O(log₂n)。...但在最坏的情况下，即构造二叉排序树输入序列是有序的，则会形成一个倾斜的单分支，此时二叉排序树的性能显著变坏，树的高度也增加为元素个数N。...如果二叉排序树是一个只有右（左）孩子的单分支（类似于有序的单链表），其平均查找长度与单链表相同，为O(n) 如果二叉排序树的左、右子树的高度差的绝对值不超过1，这样的二叉排序树称为平衡二叉树。...平衡二叉树 为了避免树的高度增长过快，降低二叉排序树的性能，我们规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差绝对值不超过1，将这样的二叉树称为平衡二叉树，简称平衡树（AVL）。...平衡二叉树可定义为它或者是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过1。 1.

1.1K3 1

判断是不是平衡二叉树

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树 平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树...解答平衡树意味着我们需要对比任何在同一个根下的左右子树的高度差，还记得之前我们计算树的高度么，使用递归方式来解决，其实这道题与算高度差不多，只是两边高度需要算出一个差值。...算法的主要思想：不断对比每两个节点的左右子树的最大高度差，注意取差的绝对值，需要小于等于1 对比完左右子树之后，需要递归左子树以及右子树进行分别判断，都满足才是平衡树 Java 代码如下： public...但是判断每个节点最大高度需要递归左右子树，需要占用 O(log2n)，所以总共占用O(Nlog2n) 空间复杂度O(n)：最差情况下，也就是树退化为链表时，递归需要使用 O(n) 的栈空间，严格意义上递归栈也需要空间...-1 : 1 + max(left, right); } }; 时间复杂度O(n)：每个节点计算一次空间复杂度O(n)：递归需要使用额外堆栈空间【作者简介】秦怀，技术之路不在一时，山高水长

1.1K2 0

经典数据结构实现与分析：顺序表，单链表，栈，队列，树结构，图结构；

队列变种：优先队列(priority queue)，队列中每个元素具有优先级，新的队列进行入队时，会根据优先级进行重新排序，重新定位到特定的位置；优先队列方便使用链表进行实现；树：树的经典结构为二叉树结构...，根为第一层，根的子节点为第二层；以此类推；树的高度或深度：节点最大层次；堂兄弟节点：父节点在同一层的节点为堂兄弟；节点的祖先：从根到节点所经分支上的所有节点；子孙：以某以节点为根的子树中任一节点都称为该节点的子孙...除d层以外，其他各层的节点数目均已达到最大值；第d层所有节点从左到右连续地紧密排列，这样的二叉树称为完全二叉树，其中满二叉树的定义是最底层的所有叶节点都在的完全二叉树；平衡二叉树：当且仅当任何节点的两棵子树的高度差不大于...1的二叉树；排序二叉树（二叉查找树，binary searcg tree）：若左子树不空，则左子树上所有节点的值都小于它的根节点的值；若右子树不空，则右子树上所有节点的值都大于它的根节点的值；...广度优先遍历(Breadth First Search): 从树的根开始，从上到下，从左到右遍历整个树的节点；深度优先遍历一般用递归实现，广度优先一般使用队列实现；一般情况下能用递归实现的大部分算法也能用堆栈来进行实现

9031 0

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

平衡二叉搜索树平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树...最后一棵不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了1。...最后再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。...之前我们讲栈与队列的时候，就说过栈其实就是递归的一种是实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。...而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。这里其实我们又了解了栈与队列的一个应用场景了。

4364 0

准备下次编程面试前你应该知道的数据结构

有没有想过它是如何工作的？其思路就是，按照最后的状态排列在先的顺序将工作的先前状态（限于特定数字）存储在内存中。这只用数组是无法实现的，因此堆栈就有了用武之地。可以把堆栈看作一堆垂直排列的书籍。...，则返回 true Top ——返回顶部元素，但不从堆栈中删除常见的堆栈面试问题：使用堆栈计算后缀表达式对堆栈中的值进行排序检查表达式中的括号是否平衡队列与堆栈类似，队列是另一种线性数据结构...isEmpty() —— 如果队列为空，则返回 true Top() —— 返回队列的第一个元素常问的队列面试问题：使用队列来实现堆栈颠倒队列中前 k 个元素的顺序使用队列生成从 1 到 n 的二进制数...链表就像一个节点链，其中每个节点包含数据和指向链中后续节点的指针等信息。有一个头指针，指向链表的第一个元素，如果列表是空的，那么它只指向 null 或不指向任何内容。...常问的树面试问题：找到一个二叉树的高度找到一个二叉搜索树中第 k 个最大值找到距离根部“k”个距离的节点找到一个二叉树中给定节点的祖先（ancestors）字典树字典树，也叫“前缀树”，是一种树形结构

1.2K1 0

30 个重要数据结构和算法完整介绍(建议收藏保存)

堆栈可以使用数组或链表来实现。它们是做什么用的？现实生活中最常见的例子是在食堂中将盘子叠放在一起。位于顶部的板首先被移除。放置在最底部的盘子是在堆栈中保留时间最长的盘子。...队列可以使用固定长度的数组、循环数组或链表来实现。它们是做什么用的？这种抽象数据类型 (ADT) 的最佳用途当然是模拟现实生活中的队列。...例如，在呼叫中心应用程序中，队列用于保存等待从顾问那里获得帮助的客户——这些客户应该按照他们呼叫的顺序获得帮助。一种特殊且非常重要的队列类型是优先级队列。...特性 ANY自平衡BST中ANY操作的摊销时间复杂度为O(log n)；在最坏的情况下，AVL 的最大高度是 1.44 * log2n（为什么？...SPT 是一种自平衡二叉树，但该算法可以使用堆（或优先级队列）来实现。我们将讨论堆解决方案，因为它的时间复杂度是 O(|E|*log |V|)。这个想法是使用图形的邻接列表表示。

2K3 1

数据结构——二叉树（续集）

~画图分析~ 怎么样~有没有体会到递归的暴力美学呢？...//根结点最后打印 LasOrder(root->left); LasOrder(root->right); printf("%c ", root->data); } 这里三种遍历相信问题不大，递归的魅力有没有体会到呢...接下来我们继续使用递归对二叉树进行操作~ 二叉树操作还是以这一个二叉树为例 二叉树结点个数这里我们来巧妙的使用递归方法求结点个数~ 原理：总结点个数 = 1 + 左子树结点个数 +右子树结点个数.../高度思路： 二叉树的深度/高度 = 1 + Max（左子树深度/高度、右子树深度/高度最大值）（如果为空返回0）代码： // 二叉树的深度/高度 int BinaryTreeDepth...这里同样需要使用队列~这里我们来画图找完全二叉树和非完全二叉树的区别~ 完全二叉树： 1.根结点入队列 2.队列不为空，取队头出队头，将左右孩子结点入队列（这里结点为空也入，方便后面判断），如此循环，到取到

821 0

BFS 算法框架套路详解

你想啊，DFS 实际上是靠递归的堆栈记录走过的路径，你要找到最短路径，肯定得把二叉树中所有树杈都探索完才能对比出最短的路径有多长对不对？...还是拿刚才我们处理二叉树问题的例子，假设给你的这个二叉树是满二叉树，节点总数为N，对于 DFS 算法来说，空间复杂度无非就是递归堆栈，最坏情况下顶多就是树的高度，也就是O(logN)。...但是你想想 BFS 算法，队列中每次都会储存着二叉树一层的节点，这样的话最坏情况下空间复杂度应该是树的最底层节点的数量，也就是N/2，用 Big O 表示的话也就是O(N)。...由此观之，BFS 还是有代价的，一般来说在找最短路径的时候使用 BFS，其他时候还是 DFS 使用得多一些（主要是递归代码好写）。...比如我们刚才讨论的二叉树最小高度的问题，你一开始根本就不知道终点在哪里，也就无法使用双向 BFS；但是第二个密码锁的问题，是可以使用双向 BFS 算法来提高效率的，代码稍加修改即可： int openLock

6882 0

七十七、二叉树的层次遍历和最大深度

本题就是用广度优先搜索，对二叉树按照层进行搜索，搜索逻辑如下图所示：根据我们熟悉的BFS搜索方法，二叉树的层次遍历，关键要用到队列，父结点出，就要判断子结点是否为空，非空则马上进入队列,类似广度优先...# Related Topics 树深度优先搜索看到该题目，首先想到的是使用递归来实现，递归的基本条件是访问到根节点（左右子树为空）；递归条件是访问左子树或右子树；中间处理逻辑是将子树深度+1，即为最终深度...# 本题中，一棵高度平衡二叉树定义为： # 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。...# Related Topics 树深度优先搜索定义一个获取当前节点高度的方法, 可以参考上面：求二叉树的最大深度左右两个子树的高度差的绝对值超过1，则为false 如果当前节点的左右子树满足高度差的绝对值不超过...DFS，递归过程中：终止条件：当DFS越过叶子节点时，返回高度0；返回值：从底至顶，返回以每个节点root为根节点的子树最大高度(左右子树中最大的高度值加1 max(left,right) + 1)

4801 0

算法笔记汇总精简版下载_算法与数据结构笔记

递归代码虽然简洁高效，但是，递归代码也有很多弊端。比如，堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等，所以，在编写递归代码的时候，一定要控制好这些副作用。递归的优缺点？...递归常见问题及解决方案 1.警惕堆栈溢出：可以声明一个全局变量来控制递归的深度，从而避免堆栈溢出。 2.警惕重复计算：通过某种数据结构来保存已经求解过的值，从而避免重复计算。...* 2.随机法：每次从要排序的区间中，随机选择一个元素作为分区点。 * 3.警惕快排的递归发生堆栈溢出，有2种解决方法，如下： ①限制递归深度，一旦递归超过了设置的阈值就停止递归。...（2）一致性哈希算法【07-二叉树】之前说的栈和队列都是线性表结构，树是非线性表结构。关于树的常用概念：根节点、叶子节点、父节点、子节点、兄弟节点，还有节点的高度、深度、层数，以及树的高度。...二叉查找树的时间复杂度分析：完全二叉树（或满二叉树），不管操作是插入、删除还是查找，时间复杂度其实都跟树的高度成正比，也就是 O(height)。

8891 0

与机器学习算法有关的数据结构

通常情况下，顶部排名最高的值将从堆中取出，以便对列表进行排序。与树不同，大多数堆只是简单地存储在一个数组中，元素之间的关系也只是隐含的。栈一个堆栈被定义为“先进后出”。...例如，libAGF库使用递归控制语言将二进制分类概括为多类。一个特殊的字符用于重复前面的选项，但是由于该语言是递归的，所以必须从相同的层次或更高的层次中提取该选项。这是由堆栈实现的。...一个明显的解决方案是一个二分法：递归地将这些类分成两组。除了分层解决方案不是解决多类问题的唯一方法之外，可以使用类似二叉树的方法来组织二进制分类器。考虑几个分区，然后用来同时解决所有类的概率。...即使你不能提出一个应用程序，我仍然认为知道诸如堆栈和队列之类的东西是很好的。你永远不知道什么时候可以派上用场。...您可以使用什么内部表示/数据结构来实现抽象数据类型？有没有包含在上面的列表中？使用二叉树，设计一个关联数组。考虑LIBSVM中的矢量类型。这怎么可以用来表示一个稀疏矩阵？

2.2K7 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云