- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/problems/count-complete-tree-nodes/description/
Given a complete binary tree, count the number of nodes.
Note:
Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Example:
Input:
1
/ \
2 3
/ \ /
4 5 6
Output: 6
求一个完全二叉树的节点个数。
我知道这个肯定有简单算法的,否则可以直接遍历去求,那样没意义。
参考了222. Count Complete Tree Nodesopen in new window的做法,在此感谢。
求完全二叉树的节点数目。注意完全二叉树和满二叉树Full Binary Tree的唯一区别是,完全二叉树最后一层的节点不满,而且假设最后一层有节点,都是从左边开始。 这样我们可以利用这个性质得到下面的结论:
1、 假如左子树高度等于右子树高度,则右子树为完全二叉树,左子树为满二叉树;
2、 假如高度不等,则左字数为完全二叉树,右子树为满二叉树;
3、 求高度的时候只往左子树来找;
可以使用上面的结论得出本题的解法:
1、 先构造一个getHeight方法,用来求出二叉树的高度这里我们只用求从根节点到最左端节点的长度;
2、 求出根节点左子树高度leftHeight和根节点右子树高度rightHeight;
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root: return 0
nodes = 0
left_height = self.getHeight(root.left)
right_height = self.getHeight(root.right)
if left_height == right_height:
nodes = 2 ** left_height + self.countNodes(root.right)
else:
nodes = 2 ** right_height + self.countNodes(root.left)
return nodes
def getHeight(self, root):
height = 0
while root:
height += 1
root = root.left
return height
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
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;
我是一名优秀的程序员,十分优秀!