二叉树直径的定义：二叉树中路径的最大长度 二叉树中路径的最大长度，可以理解所有节点的左右子树高度之和的最大值。...假设二叉树有n个节点，编号为{a1,a2,…,an}, 其对应的左右子树的高度之和为H = {h1,h2,h3,…,hn}, 则该二叉树的直径为max(H)。...struct node { int val; node *left, *right; }; int ans = 0;// 用于维护任意节点左右子树高度和的最大值 //dfs()函数的返回值是当前节点的高度
1、概念 搜索二叉树(Binary Search Tree - BST) 它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；...完全二叉树(Complete Binary Tree- CBT) 若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。...经典应用：堆 平衡二叉树(Self-balancing binary search tree) 它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。...总的一句话就是，任意节点左右子树的高度差不超过1 2、搜索二叉树的判断 思路 由于搜索二叉树的特性，根节点 > 左，根节点 < 右，那么其中序遍历的顺序必然是升序的。...思路 由于平衡二叉树要求任意左右子树的高度差不超过1。
昨天的文章讲述了二叉树的先序、中序和后序的遍历方法（递归和非递归）,但是这种遍历方法有什么意义么？...今天来讲讲这些算法可以用来做什么，只要稍加更改，我们就可以得到另外一个功能，只需要仅仅几行代码的修改！ 还记得上篇文章二叉树的分类么？今天我们要来说三种树的分类：完全二叉树、平衡二叉树和搜索二叉树！...平衡二叉树：每个节点的左子树和右子树的高度不能超过1，也就是小于等于1 搜索二叉树：按照中序遍历必定会得到一个有序的数组，也就是当前节点的值要大于左孩子的值，小于右孩子的值。...我们以下面的二叉树为例，其均符合以上的三个类别！ ?...判断二叉树的类别 是否为平衡二叉树 这里面就存在一个套路，因为判断是否为平衡二叉树的规则对于每个节点都是一致的，也就是说当前节点左子树的高度和其右子树的高度高度差不能超过1，这就很显然可以使用一个递归函数来对每个节点进行遍历
一、二叉树的前序遍历 方法一：全局变量记录节点个数 计算树的节点数: 函数TreeSize用于递归地计算二叉树中的节点数。如果树为空（即根节点为NULL），则返回0。...leftDepth + 1 : rightDepth + 1; } 三、平衡二叉树 给定一个二叉树，判断它是否是高度平衡的二叉树。...本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 /** * Definition for a binary tree node....} 四、二叉树遍历 编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。...例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
个人主页: :✨✨✨初阶牛✨✨✨ 推荐专栏1: C语言初阶 推荐专栏2: C语言进阶 个人信条: 知行合一 本篇简介:>:讲解二叉树中如何计算二叉树的结点个数,叶子结点的个数,二叉树的高度,第k...层结点的个数,以及在二叉树中如何查找查找目标值....--苏格拉底✨ 一、计算二叉树的结点个数 对于一棵 二叉树 ,如何计算它又多少个结点?...即 二叉树 的每个结点只需要知道其 左右子树 的结点个数就行. 故 二叉树 的结点个数= 左子树+ 右子树 +1(自己本身)....的基本操作就讲到这里了,后续会分享几个 二叉树 的相关oj题,希望对大家有所帮助.
是否对称 给定一个二叉树，检查它是否是镜像对称的。 image 上图为对称二叉树 image 上图的二叉树则不是镜像的 思路 判断是否是镜像，需要去判断二叉树的里侧和外侧是否相同。...空间复杂度：O(H)，其中 H 是树的高度 二叉树的最大深度 给定一个二叉树，找出其最大深度。 思路 二叉树的深度是指根节点到最远叶子节点的最长路径上的节点数。...+1为二叉树的最大深度。...可以看出, 求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。...空间复杂度：O(h)，h 为 树的高度 平衡二叉树 给定一个二叉树，判断它是否是高度平衡的二叉树。
JavaScript实现LeetCode第100题：相同的树 JavaScript实现LeetCode第101题：对称二叉树 JavaScript实现LeetCode第226题：翻转二叉树 这几道题其实很相似...相同的树 题目描述 给定两个二叉树，编写一个函数来检验它们是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。...isSameTree(p.right, q.right); }; 时间复杂度：O(n)，n 为树的节点个数，因为每个节点都要访问一次 空间复杂度：最优情况（完全平衡二叉树）时为 O(log(N))，...对称二叉树 题目描述 给定一个二叉树，检查它是否是镜像对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。...翻转二叉树 题目描述 翻转一棵二叉树。
二叉树的最大路径和，枚举二叉树的每一个节点，通过当前节点最大路径和是， 当前节点左子树的最大路径和+root->val+当前节点右子树的最大路径。
二叉树的实现 定义结构体 我们首先定义一个结构来存放二叉树的节点 结构体里分别存放左子节点和右子节点以及节点存放的数据 typedef int BTDataType; typedef struct BinaryTreeNode...所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。...遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础 按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历： 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前...设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历...二叉树是否为完全二叉树 判断是否未完全二叉树的条件是什么呢 就是层序遍历完成时中间有无空节点！
题目 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。...示例： 二叉树：[3,9,20,null,null,15,7], 返回其层次遍历结果： [ [3], [9,20], [15,7] ] 来源：力扣（LeetCode） 链接：https...先记录现在队列里面的元素个数n，n就是此二叉树这一深度拥有的节点数，然后循环n次，把n个节点的左右孩子都添加到队列里面，每次循环完把队列前面的元素pop到一个动态数组里，这样就能实现一个深度的节点为一个数组了...brr.push(node->right); } crr.push_back(brr.front()->val); //每次循环把队列的头元素的值添加到一个数组里
1 题目描述 给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明：叶子节点是指没有子节点的节点。...·空间复杂度:O(H)，其中H是树的高度。空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为O(N)。...平均情况下树的高度与节点数的对数正相关，空间复杂度为O(log N)。 方法二:广度优先搜索 同样，我们可以想到使用广度优先搜索的方法，遍历整棵树。...当我们找到一个叶子节点时，直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度—定最小。 复杂度分析 时间复杂度:O(N)，其中N是树的节点数。对每个节点访问一次。...·空间复杂度:O(N)，其中N是树的节点数。空间复杂度主要取决于队列的开销，队列中的元素个数不会超过树的节点数。
，什么叫二叉树的重建呢？...比方说给你一棵二叉树的前序遍历顺序和中序遍历顺序，要求你求出这颗二叉树的后序遍历顺序。...主要还是根据前序遍历和中序遍历的顺序来一步步重建树节点 整个过程的代码，也是这个问题的核心代码： // 重建二叉树以第 n 个节点为根节点的子二叉树，l 为二叉树节点的左边界，r 为右边界 void rec...// 重建二叉树的第 n 个节点为根节点的子二叉树, l 为二叉树节点的左边界，r 为右边界 void rec(int l, int r, int n) { if(l >= r) {...我们可以手工构造出这棵二叉树： ? 根据二叉树的遍历顺序，我们可以很容易得到该二叉树的后续遍历，和程序执行的结果一样。
前言 如果一颗二叉树和它的镜像一样，那么它就是对称的。实现一个函数用于判断一颗二叉树是否对称，你会怎么做？ 本文将分享一种解决方案，欢迎各位感兴趣的开发者阅读本文。...实现思路 在上一篇文章二叉树的镜像中我们知道了此问题的解决方案是前序遍历，那么我们可以修改下前序遍历算法，父节点遍历后，先遍历它的右子节点，再遍历它的左子节点，我们把这种算法称为：对称前序遍历 如下图所示的两棵树...对称前序遍历：8, 9, 5, 7, 6, 7, 5 经过对比后，我们发现树A的两种遍历方法得到的结果是一样的，那么它就是对称的；树B的结果不同，它就不是对称的。...image-20220726203435638 如果有一颗不完全二叉树，它的所有节点都相同，他是对称的吗？...7 }, right: { key: 5 } } }; const isSymmetric = SymmetricBinaryTree(tree); console.log(tree, "是否为对称二叉树
1.构建方法 二叉树的前序、中序和后序序列中的任何一个都不能唯一确定一棵二叉树，二叉树的构建主要有两大方法。...第一种是中序序列和前、中，层次序列任一组合唯一确定一颗二叉树； 第二种是根据二叉树对应的扩充二叉树的先序或者后序序列来确定。注意扩充二叉树的中序遍历序列是不能唯一确定二叉树的结构。...上图中扩展二叉树的中序遍历序列为：#B#D#A#C#，那么也可以对应为下面的扩展二叉树： ?...假设扩展二叉树的前序遍历序列由键盘输入，root 为指向根结点的指针，二叉链表的建立过程是：首先输入根结点，若输入的是一个“#”字符，则表明该二叉树为空树，即 root=NULL；否则输入的字符应该赋给...6.扩充二叉树后序序列构建 本人尚未研究，请知道的网友留言指教。 7.小结 本文内容还不够完善，如先序+中序构建二叉树可以用非递归的方法来实现，等等，鄙人后续会继续完善的。 ----
题目 给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明：叶子节点是指没有子节点的节点。...root = [3,9,20,null,null,15,7] 输出：2 示例 2： 输入：root = [2,null,3,null,4,null,5,null,6] 输出：5 提示： 树中节点数的范围在...思路 二叉树每个节点的路径最小(最大)为左子树和右子树中最小(最大)路径加上它自己 /** * Definition for a binary tree node.
题目描述 二叉树两个结点的距离是一个结点经过双亲结点，祖先结点等中间结点到达另一个结点经过的分支数。二叉树结点的最大距离是所有结点间距离的最大值。例如，下图所示二叉树结点最大距离是3，C和D的距离。...二叉树用先序遍历顺序创建，#表示空树。计算二叉树结点最大距离和最大距离的两个结点(假设二叉树中取最大距离的两个结点唯一）。...输入 测试次数T 第2行之后的T行，每行为一棵二叉树先序遍历结果（#表示空树） 输出 对每棵二叉树，输出树的结点最大距离和最大距离的结点，输出格式见样例。...而距离可以用深度来计算，这个满足条件的解的树的左右子树的深度加起来就是最大距离。 也就是说，我们需要找出每棵树的左右子树的深度之和，然后找出最大的就是我们需要的解，这个用一个递归函数可以完成。...对于一颗树，它的最深的末端叶子节点应该在深度最大的子树那里，所以我们需要知道子树的深度，再引入一个求深度的函数，这个求树的深度的函数非常NB，是一个学长教的，只用了三行代码搞定。
前言 给定一颗二叉树，如何获取它的镜像？本文将跟大家分享这个问题的解决方案，欢迎各位感兴趣的开发者阅读本文。 思路分析 当我们把一张写有文字的纸放在镜子前面，你看到的内容正好与你写的内容是相反的。...那么我们就可以依据照镜子的经验画出它的镜像了，如下所示： 镜像前后的两棵树根节点相同 镜像后的树与镜像前相比：它们的左、右子节点交换了位置 image-20220713220838785 通过观察后，...我们就得出了一颗树的镜像过程：先序遍历这棵树的每个节点，如果遍历到的节点有子节点，就交换它的两个子节点。...当交换完所有非叶节点的左、右子节点之后，就得到了树的镜像。...对树的遍历不了解的开发者，请移步我的另一篇文章：先序遍历 实现代码 想清楚思路后，我们就可以很顺利的写出代码了，如下所示： export function MirrorImageOfTree(node:
题目描述 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 解题思路 法一：递归法。...求二叉树的深度，就是求左子树、右子树的中深度最大的加上一个根节点，依此递归即可。 法二：层次遍历。每遍历一层，deep 加 1，直接到最后一层，输出 deep。
题意 请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。.../ \ 1 1 / \ / \ 6 4 4 6 B). 3 / \ 1 2 / \ / \ 7 4 5 6 A 与 B 在结构上都是对称的，...但是本题的题意是指也对应，所以 A 树是一颗对称二叉树，B 树不是一颗对称的二叉树。...思路 观察上方的样例可得结论： 根节点的左右节点的值是相同的 除根节点外，某节点的右子树与兄弟节点的左子树的值相同 除根节点外，某节点的左子树与兄弟节点的右子树的值相同 代码实现 /* public class...right) && fun(n1.right, n2.left); } return false; } } 原题地址 牛客网：对称的二叉树
题目描述 请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。 解题思路 法一：递归。...根节点的左右子树相同，左子树的左子树和右子树的右子树相同，左子树的右子树和右子树的左子树相同即可。 法二：非递归。非递归也是一样，采用栈或队列存取各级子树根节点。 参考代码 法一：递归。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
