- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
卡哥建议: 什么是深度,什么是高度,如何求深度,如何求高度,这里有关系到二叉树的遍历方式。 大家要先看视频讲解,就知道以上我说的内容了,很多录友刷过这道题,但理解的还不够.
题目链接/文章讲解/视频讲解:https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html 。
二叉树节点的 深度 :指 从根节点到该节点 的最长简单路径边的条数或者节点数(取决于深度从0开始还是从1开始) 。
二叉树节点的 高度 :指 从该节点到叶子节点 的最长简单路径边的条数或者节点数(取决于高度从0开始还是从1开始) 。
而根节点的高度就是二叉树的最大深度 ,所以本题中我们 通过后序 求的根节点高度来求的二叉树最大深度。用什么遍历顺序这里多看卡哥视频理解吧.
先求它的左子树的深度,再求右子树的深度,最后取左右深度最大的数值 再+1 (加1是因为算上当前中间节点)就是目前节点为根节点的树的深度.
1
int
getdepth(TreeNode*
node) {
2
if
(node == NULL)
return
0
;
3
int
leftdepth = getdepth(node->left);
//
左
4
int
rightdepth = getdepth(node->right);
//
右
5
int
depth =
1
+ max(leftdepth, rightdepth);
//
中
6
return
depth;
7
}
8
int
maxDepth(TreeNode*
root) {
9
return
getdepth(root);
10
}
。
卡哥建议: 先看视频讲解,和最大深度 看似差不多,其实 差距还挺大,有坑.
题目链接/文章讲解/视频讲解:https://programmercarl.com/0111.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6.html 。
最小深度 是 从根节点到最近叶子节点 的最短路径上的节点数量.
二叉树节点的 深度 :指 从根节点到该节点 的最长简单路径边的条数或者节点数(取决于深度从0开始还是从1开始) 。
二叉树节点的 高度 :指 从该节点到叶子节点 的最长简单路径边的条数或者节点数(取决于高度从0开始还是从1开始) 。
那么使用 后序遍历 ,其实求的是根节点到叶子节点的最小距离,就是求高度的过程,不过这个最小距离 也同样是最小深度。 注意是叶子节点。什么是叶子节点,左右孩子都为空的节点才是叶子节点!如果根节点的左子树是空的话,那就从右子树开始找叶子节点.
求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑.
1
int
getDepth(TreeNode*
node) {
2
if
(node == NULL)
return
0
;
3
int
leftDepth = getDepth(node->left);
//
左
4
int
rightDepth = getDepth(node->right);
//
右
5
//
中
6
//
当一个左子树为空,右不为空,这时并不是最低点
7
if
(node->left == NULL && node->right !=
NULL) {
8
return
1
+
rightDepth;
9
}
10
//
当一个右子树为空,左不为空,这时并不是最低点
11
if
(node->left != NULL && node->right ==
NULL) {
12
return
1
+
leftDepth;
13
}
14
int
result =
1
+
min(leftDepth, rightDepth);
15
return
result;
16
}
17
18
int
minDepth(TreeNode*
root) {
19
return
getDepth(root);
20
}
卡哥建议: 需要了解,普通二叉树 怎么求,完全二叉树又怎么求 。
题目链接/文章讲解/视频讲解:https://programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html 。
普通二叉树 先求它的左子树的节点数量,再求右子树的节点数量,最后取总和再加一 (加1是因为算上当前中间节点)就是目前节点为根节点的节点数量.
在完全二叉树中,底层节点一定是从左边开始连续的,只有左边的也行,只有右边的不行。若最底层为第 h 层,则该层包含 1~ 2^(h-1) 个节点.
满二叉树 的任意节点,要么度为0,要么度为2.换个说法即要么为叶子结点,要么同时具有左右孩子.
完全二叉树只有两种情况,情况一:就是满二叉树,情况二:最后一层叶子节点没有满.
对于情况一,可以直接用 2^树深度 - 1 来计算,注意这里根节点深度为1.
。
。
对于情况二, 如果整个树不是满二叉树,就递归其左右孩子,直到遇到满二叉树为止,用公式计算这个子树(满二叉树)的节点数量。这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢? 在完全二叉树中,如果递归向左遍历的深度等于递归向右遍历的深度,那说明就是满二叉树.
1
int
countNodes(TreeNode*
root) {
2
if
(root == nullptr)
return
0
;
3
TreeNode* left = root->
left;
4
TreeNode* right = root->
right;
5
int
leftDepth =
0
, rightDepth =
0
;
//
这里初始为0是有目的的,为了下面求指数方便
6
while
(left) {
//
求左子树深度
7
left = left->
left;
8
leftDepth++
;
9
}
10
while
(right) {
//
求右子树深度
11
right = right->
right;
12
rightDepth++
;
13
}
14
if
(leftDepth ==
rightDepth) {
15
return
(
2
<< leftDepth) -
1
;
//
这里记住就行,注意(2<<1) 相当于2^2,所以leftDepth初始为0,即2^1 - 1
16
}
17
return
countNodes(root->left) + countNodes(root->right) +
1
;
18
}
最后此篇关于代码随想录算法训练营第十六天|104.二叉树的最大深度111.二叉树的最小深度222.完全二叉树的节点个数的文章就讲到这里了,如果你想了解更多关于代码随想录算法训练营第十六天|104.二叉树的最大深度111.二叉树的最小深度222.完全二叉树的节点个数的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
1。 Set 的 parallelStream 没有使用足够的线程。 Java8 parallelStream 不能完全并行工作。在我的计算机中,当任务数小于处理器数时,java8 集的 parall
我想将位置发送到 Google Geocoding API,因此我想用 + 替换文本中的任何空格或逗号(因为可以接收)。 例如,所有这些样本应返回 Glentworth+Ireland: Glentw
所以我需要为将要上传的图像文件生成较小的预览,并且我必须在每个文件名的末尾附加“_preview”。 目前我正在这样做: uploadFile.map((file) => { if (fi
我们可以用参数定义类型同义词,这在与实际类型一起使用时效果很好: type MyType t = t String String data Test a b = Test a b f :: MyTyp
给定一个包含一些 TGraphic 后代的 Delphi TPicture,我需要计算像素颜色和不透明度。我认为我必须为每个类提供不同的实现,并且我认为我已经涵盖了 TPngImage。 32 位位图
我正在调试 Powershell 项目。我正在使用 Import-Module 从我的 C# dll 加载 PS 模块,一切正常。尽管调用 Remove-Module 并不会完全卸载模块,因为 DLL
有没有办法在ElasticSearch中要求完整(尽管不一定精确)匹配? 例如,如果一个字段具有术语"I am a little teapot short and stout",我想匹配" i am
我正在尝试根据日期范围连接两个表。 表A格式为: ID CAT DATE_START DATE_END 1 10 2018-01-01 2020-12-31 2
我最近加入了一家公司,在分析他们的环境时,我注意到 SharePoint web.config 的信任级别设置为“完全”。我知道这绝对是一个糟糕的做法,并且希望 stackoverflow 社区能够帮
我构建了一个完全依赖 AJAX 的 php/js 应用程序,因此没有任何内容是静态的。 我正在尝试找到一种方法来转换基于内容的广告,该广告使用 AJAX 交付的内容作为关键字。 Google 的 Ad
我正在尝试根据日期范围连接两个表。 表A格式为: ID CAT DATE_START DATE_END 1 10 2018-01-01 2020-12-31 2
我熟悉 FileSystemWatcher 类,并使用它进行了测试,或者我使用快速循环进行了测试,并在目录中列出了类型文件的目录列表。在这种特殊情况下,它们是 zip 压缩的 SDF 文件,我需要解压
按照 Disqus 上的教程进行操作时,评论框不会呈现。从 disqus 上找到的管理员看来,它的设置似乎是正确的。 var disqus_config = function () { this
是否可以使用 Cython 将 Python 3 应用程序完全编译/链接为可执行格式(当然假设所有使用的模块都是 cythonable)。 我在 Linux 下工作,我希望获得一个依赖性尽可能小的 E
我有一个 C# 控制台应用程序,而不是运行预构建步骤(以获取 NuGet 包)。 当我调试这个时,我想传入一个参数并显示控制台。当我不调试它时,我不想看到它。我什至不希望它在那里闪烁一秒钟。 我找到了
我在 n 个节点上有一个完整的 19 元树。我标记所有具有以下属性的节点,即它们的所有非根祖先都是最年长或最小的 child (包括根)。我必须为标记节点的数量给出一个渐近界限。 我注意到 第一层有一
我正在阅读一篇关于 Java Volatile 关键字的文章,遇到了一些问题。 click here public class MyClass { private int years;
一本书中写道——“如果问题 A 是 NP-Complete,则存在解决 A 的非确定性多项式时间算法”。但据我所知,"is"——NP 完全问题的答案可以在多项式时间内“验证”。我真的很困惑。能否使用非
考虑以下问题: 有N个硬币,编号为1到N。 你看不到它们,但是给出了关于它们的 M 个事实,形式如下: struct Fact { set positions int num_head
我想制作一个包装数字类型的类型(并提供额外的功能)。 此外,我需要数字和包装器可以隐式转换彼此。 到目前为止我有: template struct Wrapper { T value;
我是一名优秀的程序员,十分优秀!