友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
919. 完全二叉树插入器
完全二叉树 是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。
设计一种算法，将一个新节点插入到一棵完全二叉树中，并在插入后保持其完整。
实现 CBTInserter 类:
-
CBTInserter(TreeNode root)使用头节点为root的给定树初始化该数据结构； -
CBTInserter.insert(int v)向树中插入一个值为Node.val == val`的新节点 `TreeNode。使树保持完全二叉树的状态，并返回插入节点TreeNode的父节点的值； -
CBTInserter.get_root()将返回树的头节点。
示例 1：
输入 ["CBTInserter", "insert", "insert", "get_root"] [[[1, 2]], [3], [4], []] 输出 [null, 1, 2, [1, 2, 3, 4]] 解释 CBTInserter cBTInserter = new CBTInserter([1, 2]); cBTInserter.insert(3); // 返回 1 cBTInserter.insert(4); // 返回 2 cBTInserter.get_root(); // 返回 [1, 2, 3, 4]
提示：
-
树中节点数量范围为
[1, 1000] -
0 <= Node.val <= 5000 -
root是完全二叉树 -
0 <= val <= 5000 -
每个测试用例最多调用
insert和get_root操作104次
思路分析
广度优先队列。可以缓存要插入的父节点队列，加快速度。
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-09-05 00:14:07
*/
class CBTInserter {
private TreeNode root;
private Queue<TreeNode> queue = new LinkedList<>();
public CBTInserter(TreeNode root) {
this.root = root;
}
public int insert(int val) {
if (queue.isEmpty()) {
queue.offer(root);
while (true) {
int size = queue.size();
Queue<TreeNode> next = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.peek();
if (node.left == null || node.right == null) {
break;
} else {
queue.poll();
next.offer(node.left);
next.offer(node.right);
}
}
if (queue.isEmpty()) {
queue.addAll(next);
} else {
break;
}
}
}
TreeNode peek = queue.peek();
if (peek.left == null) {
peek.left = new TreeNode(val);
} else {
peek.right = new TreeNode(val);
queue.poll();
}
return peek.val;
}
public TreeNode get_root() {
return root;
}
}