我们可以使用 sizeof 运算符找到数组的大小，如下所示。...// 查找 arr[] 的大小并存储在 'size' int size = sizeof(arr)/sizeof(arr[0]); 我们可以在不使用 sizeof 运算符的情况下做同样的事情吗？...方法一（自己写sizeof） 给定一个数组（你不知道数组中元素的类型），不使用sizeof运算符，求数组中元素的总数？...一个解决方案是我们自己写的sizeof操作符 // C++ 程序通过编写我们的 sizeof 来查找数组的大小 #include using namespace std;...可以使用表达式找出数组 A 中的元素数 int size = *(&arr + 1) - arr; // C++ 程序通过使用指针 hack 来查找数组的大小。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树 平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树...解答 平衡树意味着我们需要对比任何在同一个根下的左右子树的高度差，还记得之前我们计算树的高度么，使用递归方式来解决，其实这道题与算高度差不多，只是两边高度需要算出一个差值。...算法的主要思想： 不断对比每两个节点的左右子树的最大高度差，注意取差的绝对值，需要小于等于1 对比完左右子树之后，需要递归左子树以及右子树进行分别判断，都满足才是平衡树 Java 代码如下： public...但是判断每个节点最大高度需要递归左右子树，需要占用 O(log2n)，所以总共占用O(Nlog2n) 空间复杂度O(n)：最差情况下，也就是树退化为链表时，递归需要使用 O(n) 的栈空间，严格意义上递归栈也需要空间...-1 : 1 + max(left, right); } }; 时间复杂度O(n)：每个节点计算一次 空间复杂度O(n)：递归需要使用额外堆栈空间 【作者简介】 秦怀，技术之路不在一时，山高水长
编码面试主要包括数据结构和基于算法的问题，以及一些诸如如何在不使用临时变量的情况下交换两个整数这样的逻辑问题？ 我认为将编程面试问题划分到不同的主题区域是很有帮助的。...我在面试中经常看到的主题区域是数组、链表、字符串、二叉树，以及源于算法的问题（例如字符串算法，排序算法，如 quicksort 或基数排序，以及其他杂项），这就是你能在这篇文章中找到主要内容。...解决数组问题的关键是，你要对数组这种数据结构有一个深刻的认识，同时还要了解基本的程序流程如循环、递归以及基本的操作符。...下面是一些经常问到的基于二叉树的面试题，你可以拿来练习： 1、二叉搜索树是如何实现的？ 2、如何在给定二叉树上实现前序遍历？ 3、不使用递归如何按照前序遍历给定二叉树？...4、如何在给定二叉树上实现中序遍历？ 5、不使用递归情况下如何使用中序遍历输出给定二叉树所有节点？ 6、如何实现后序遍历算法？ 7、如何不使用递归实现二叉树的后续遍历？
下面是关于链表的一些最常见、热门的面试问题，大家可以着重练习： ▌1.如何在一次递归后找到单链表的中间元素？...解决方法和代码： http://www.java67.com/2016/07/how-to-reverse-singly-linked-list-in-java-example.html ▌4.如何在没有递归的情况下反转单链表...因此，你会发现很多问题基于它们的问题，如计算节点数，如何进行遍历，计算深度，判断它们是否平衡。 解决二叉树问题的关键是要有扎实的知识理论，如什么是二叉树的大小或深度，什么是叶，以及什么是节点。...解决方法与代码： http://www.java67.com/2016/08/binary-tree-inorder-traversal-in-java.html ▌5.在不使用递归的情况下，如何使用中序遍历输出给定二叉树的所有节点...解决方法与代码： http://www.java67.com/2016/10/binary-tree-post-order-traversal-in.html ▌7.在不使用递归的情况下，如何对二叉树进行后序遍历
，得到这个数组的全排列的数组，如[2,1,3,4]，•[2,1,4,3]。。。。...二叉树前中后遍历 二叉树层次遍历 二叉树深度优先遍历(递归、非递归) 二叉树广度优先遍历(递归、非递归) 和为n的二叉树路径 二叉树深度 二叉树是否对称 链表反转 红黑树有啥特性?...给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。...要求使用尽量少的空间和时间。...200万行数据，如何在在每一行的尾部追加一个字符； 求一个字符串中最长不重复子串的长度 三个有符号的整型（long）数a, b, c，怎么判断a+b > c?
二叉树简介 二叉树的相关概念，如，树高度，节点层数，节点度数，路径，叶节点，分支节点，根节点，父节点，左节点，右节点，兄弟节点，祖先节点，子孙节点，左子树，右子树等基本概念，不再赘述，可参见百度百科：二叉树...一维数组可以作为完全二叉树的存储结构，堆排序使用的数据结构就是完全二叉树。...如下如所示，一棵普通二叉树及其扩充二叉树： image.png （4）平衡二叉树 是一棵空树或它的任意节点的左右两个子树的高度差的绝对值不超过1。...这样子我们就在前序序列和中序序列中找到了左右子书对应的子序列，然后再递归处理即可。...如果P不存在左孩子和右孩子，则可以直接访问它并出栈； （b）如果R存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点并出栈； （c）若非上述两种情况，则将R的右孩子和左孩子依次入栈
本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。...：如果二叉树的每个节点的左右子树的高度差的绝对值不超过 1，则是平衡二叉树。...根据题目定义，解题思路如涌泉般喷发，老规矩，递归破题(若一棵二叉树是平衡二叉树，必须满足其所有子树也都是平衡二叉树才行)，且递归的顺序可以是自顶向下或者自底向上，如上两种递归顺序我都给大家讲解一下。...方法一：自顶向下的递归 自顶向下顺序，这做法就类似于二叉树的前序遍历，即对于当前遍历到的节点： 首先计算左右子树的高度，如果左右子树的高度差是否不超过1， 再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡...使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 O(n)。 空间复杂度：O(n)，其中n是二叉树中的节点个数。
树不能为空，即树至少有一个结点；二叉树可以为空，因为二叉树是一种为了存储数据而创造出来的结构 从上图可以看出： 结点的度最大为2 二叉树的子树有次序之分，左子树和右子树不能颠倒 任何的二叉树都是由以下几种情况构成的...而完全二叉树的数组存储方式，其实就是堆的基本结构。在现实中使用中，也只有堆会用数组来存储。...二叉树的链式存储又分为二叉链和三叉链，当前使用的主要是二叉链，以后的红黑树等就会用到三叉链。...由于非完全二叉树会造成空间存储上的不连续，因此一般**只有完全二叉树才使用顺序存储** 物理存储上说数组，逻辑存储上是把数组想形成完全二叉树 如何在数组中找到某个结点的父结点或子结点呢 根据二叉树的性质...为了降低学习成本，先在这里手动构建一个不标准的二叉树，方便学习的理解 ```c typeof int BTDataType; typeof struct BinaryTreeNode { BTDataType
空间复杂度：O(height)：height为二叉树的最大深度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(logN)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。...翻转二叉树思路：方法一使用广度优先遍历，在遍历树的过程中，交换当前层级下的左右子树方法二使用递归解决，递归最重要的是定义子问题。...空间复杂度：O(height)：height为二叉树的最大深度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(logN)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。...;复杂度分析：时间复杂度：O(n)：n为二叉树节点数。空间复杂度：O(n)：n为二叉树节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)。...空间复杂度：O(n)：最差情况下，空间复杂度为O(n)。二叉树的所有路径思路：本题考虑使用深度优先遍历。如果当前节点有左子树或右子树，就递归调用函数，直到左右子树都不存在，此时就是我们要找的的路径。
简介 二叉树的相关概念，如，树高度，节点层数，节点度数，路径，叶节点，分支节点，根节点，父节点，左节点，右节点，兄弟节点，祖先节点，子孙节点，左子树，右子树等基本概念，不再赘述。...一维数组可以作为完全二叉树的存储结构，堆排序使用的数据结构就是完全二叉树。...4、平衡二叉树 是一棵空树或它的任意节点的左右两个子树的高度差的绝对值不超过1 二叉树的应用场景 普通的二叉树，很难构成现实的应用场景，但因其简单，常用于学习研究，平衡二叉树则是实际应用比较多的。...2、红黑树: 平衡二叉树，广泛用在C++的STL中。如map和set都是用红黑树实现的。还有Linux文件管理。 3、B/B+树: 用在磁盘文件组织 数据索引和数据库索引。...参考链接 二叉树的重建，只能在提供前序+中序，或者后序+中序的情况下，才可以正常的重构。
在我之前的文章栈中讲到，栈可以将递归转化成循环，故二叉树的很多递归实现的操作，都可以依靠栈来转换成循环，并且写法并不困难，但在该篇文章中，我并没用用非递归的方法实现这些方法，如果有兴趣的朋友，可以自己尝试以下非递归的写法...如上图所示，层序遍历的结果应该是 A B C D E F G 如果要使用层序遍历遍历二叉树的节点，那么就需要使用到之前我们学习的数据结构，也就是队列： 以上图为例： 我们要想按每一层的从左到右的顺序来打印二叉树...，我们就需要将二叉树的每一层的节点从左到右存在某一种结构中，再这种情况下，我们使用栈来存放二叉树的节点； 首先我们先创建一个队列，我们先将A节点存入队列中 我们将队列中的队头元素，也就是A节点弹出来并进行打印...，根节点，右子树，那么，只要我们在中序遍历中找到二叉树的根节点，他的左边的元素都是他的左树，右边的元素都是他的右树； 如图： 依然用之前的二叉树的图 该树的前序遍历的结果为： A B D E C...(tree.getKNodeCount(root, 3)); } } 获取二叉树的高度： 二叉树的高度是左右子树中最高的一颗树决定的，所以二叉树的高度就为左右子树的高度的最大值：
平衡二叉树是什么鬼？ 满足如下两个条件的二叉树称为“平衡二叉树”： 首先它得是二分查找树 然后它的左右子树的高度相差不超过1 ? 图1 平衡二叉树 ?...对于问题2，取决于问题1采用哪种方式——如果采用递归式算法，那么在递归的时候，也顺便把高度递归计算了；如果采用非递归式，那么就在自底向上归并的时候，动态计算高度。 问题3才是真正的新鲜问题。...这样变换之后，A、A的左子树下降，B、B的右子树上升，高度差变小。 因为任意非叶子节点A，它的值都比其左孩子C的值大，所以它可以变成C的右孩子。...此时H(A)≥H(B.Right)+2，这意味着“旋转”后，B节点的左子树高度与右子树高度相差超过1！ 貌似“旋转”对这种情况不凑效了，怎么办呢？ 先来分析一下不凑效的根因到底是什么。...二分查找树》中的节点删除算法； 但是平衡二叉树还是特殊的二分查找树，它还要满足左右子树高度相差不超过1的要求。当按照上面的算法删除节点之后，可能会不满足这个要求，因此要进行调整。
那递归到什么位置？我们不继续深层次递归了呢？开始返回上一层呢？也很简单，当我们遇到空结点时，就该归了。...1.当我们的root也就是根节点等于NULL时，其实能说明两种情况，第一种，这个树本来就是空树，第二种当我们遇到空结点时也说明递归要结束了 2.当我们遇到叶子节点时，递归也应该结束了，返回1的高度...(套用相同的树接口) 另一棵树的子树 我们先来分析递归的结束条件，当我们在左边的树中，一直找到NULL了，那肯定说明左边的树中没有我们右边的树，还有一种情况就是当我们在左边的树中找到我的subRoot了...//1.就是如果我从左边的树中找到我的右边的树了，那就递归结束了 //2.或者来root以及root的左和右子树中找了半天，到NULL了都还没找到，那递归也应该结束了 5.二叉树遍历(注意下标 i 的参数设计...平衡二叉树 递归结束条件： 1.二叉树为空树时，不用比较就是平衡二叉树 2.二叉树的左右子树高度差大于1时，递归结束，不为平衡二叉树 单层递归逻辑： 我们比较每一个根节点下的左右子树的高度差是否符合要求即可
[8p5mftxql0.png] 如上图二叉树，它的访问顺序为： A-B-D-E-C-F-G 到这里，我们思考一个问题？虽然我们用递归的方式根据DFS的思想顺利完成了题目。...但是这种方式的缺点却显而易见。因为在递归中，如果层级过深，我们很可能保存过多的临时变量，导致栈溢出。这也是为什么我们一般不在后台代码中使用递归的原因。...二叉搜索树（Binary Search Tree），（又：二叉查找树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空...你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 NULL。...本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
基于二叉树的性质，我们可以采用分治法：二叉树的节点总数是其左子树的节点数加上右子树的节点数，再加上根节点本身 基本步骤： 递归的基准情况：如果当前节点为NULL，意味着到达了叶子节点的外部（空树），返回...叶子节点定义为没有左右子树的节点。基于递归的方法，我们可以遍历整棵树，并在遇到叶子节点时对计数器进行增加。 递归的基准情况：如果当前节点为NULL，意味着到达叶子节点的外部（空树），直接返回0。...测试： 2.3 获取树的高度 获取二叉树的高度（或深度）的基本思路是遵循分治法原则，即递归地计算二叉树每个节点的左右子树的高度，并从中选择最大的一个，然后加1（当前节点在路径上增加的高度）来得到以该节点为根的子树的总高度...树的总高度即是从根节点到最远叶子节点的最长路径上的节点数。 递归基准：如果当前的节点为NULL，意味着到达了叶子节点的外部（空树），其高度为0。 递归地检查：递归地计算左子树的高度和右子树的高度。...最后，经过左子树和右子树的递归处理后，回到当前的节点，并使用free(root);释放掉该节点占用的内存。
1 题目描述 给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。...：二叉树的每个节点的左右子树的高度差的绝对值不超过 11，则二叉树是平衡二叉树。...根据定义，一棵二叉树是平衡二叉树，当且仅当其所有子树也都是平衡二叉树，因此可以使用递归的方式判断二叉树是不是平衡二叉树，递归的顺序可以是自顶向下或者自底向上。...具体做法类似于二叉树的前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 11，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。...对于平均的情况，一棵树的高度h满足O(h)= O(logn)，因为d<h，所以总时间复杂度为O(n logn)。对于最坏的情况，二叉树形成链式结构，高度为O(n)，此时总时间复杂度为o(n²)。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
对象存储
云直播
