- 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/complete-binary-tree-inserter/description/
Acomplete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
Write a data structure CBTInserter
that is initialized with a complete binary tree and supports the following operations:
Example 1:
Input: inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
Output: [null,1,[1,2]]
Example 2:
Input: inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
Output: [null,3,4,[1,2,3,4,5,6,7,8]]
Note:
1、 Theinitialgiventreeiscompleteandcontainsbetween1and1000nodes.;
2、 CBTInserter.insertiscalledatmost10000timespertestcase.;
3、 Everyvalueofagivenorinsertednodeisbetween0and5000.;
编写一个完全二叉树的数据结构,需要完成构建、插入、获取root三个函数。函数的参数和返回值如题。
周赛第三题,因为第二题我不会,就把这个题给放弃了……现在一看很简单啊。
完全二叉树是每一层都满的,因此找出要插入节点的父亲节点是很简单的。如果用数组tree保存着所有节点的层次遍历,那么新节点的父亲节点就是tree[(N -1)/2],N是未插入该节点前的树的元素个数。
构建树的时候使用层次遍历,也就是BFS把所有的节点放入到tree里。插入的时候直接计算出新节点的父亲节点。获取root就是数组中的第0个节点。
时间复杂度是O(N),空间复杂度是O(N)。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class CBTInserter(object):
def __init__(self, root):
"""
:type root: TreeNode
"""
self.tree = list()
queue = collections.deque()
queue.append(root)
while queue:
node = queue.popleft()
self.tree.append(node)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
def insert(self, v):
"""
:type v: int
:rtype: int
"""
_len = len(self.tree)
father = self.tree[(_len - 1) / 2]
node = TreeNode(v)
if not father.left:
father.left = node
else:
father.right = node
self.tree.append(node)
return father.val
def get_root(self):
"""
:rtype: TreeNode
"""
return self.tree[0]
# Your CBTInserter object will be instantiated and called as such:
# obj = CBTInserter(root)
# param_1 = obj.insert(v)
# param_2 = obj.get_root()
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
C++代码如下:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class CBTInserter {
public:
CBTInserter(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front(); q.pop();
if (!node) continue;
tree.push_back(node);
q.push(node->left);
q.push(node->right);
}
}
int insert(int v) {
TreeNode* node = new TreeNode(v);
tree.push_back(node);
TreeNode* parent = tree[tree.size() / 2 - 1];
if (!parent->left)
parent->left = node;
else
parent->right = node;
return parent->val;
}
TreeNode* get_root() {
return tree[0];
}
private:
vector<TreeNode*> tree;
};
/**
* Your CBTInserter object will be instantiated and called as such:
* CBTInserter* obj = new CBTInserter(root);
* int param_1 = obj->insert(v);
* TreeNode* param_2 = obj->get_root();
*/
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
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;
我是一名优秀的程序员,十分优秀!