LeetCode 题解工作台
完全二叉树插入器
完全二叉树 是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。 设计一种算法，将一个新节点插入到一棵完全二叉树中，并在插入后保持其完整。 实现 CBTInserter 类: CBTInserter(TreeNode root) 使用头节点为 root …
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们可以使用一个数组 来存储完全二叉树的所有节点。在初始化时，我们使用一个队列 来层序遍历给定的树，并将所有节点存储到数组 中。 在插入节点时，我们可以通过数组 来找到新节点的父节点 。然后我们创建一个新节点 ，将其插入到数组 中，并将 作为 的左子节点或右子节点。最后返回 的值。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
完全二叉树 是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。
设计一种算法，将一个新节点插入到一棵完全二叉树中，并在插入后保持其完整。
实现 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 <= 5000root是完全二叉树0 <= val <= 5000- 每个测试用例最多调用
insert和get_root操作104次
解题思路
方法一：BFS
我们可以使用一个数组 来存储完全二叉树的所有节点。在初始化时，我们使用一个队列 来层序遍历给定的树，并将所有节点存储到数组 中。
在插入节点时，我们可以通过数组 来找到新节点的父节点 。然后我们创建一个新节点 ，将其插入到数组 中，并将 作为 的左子节点或右子节点。最后返回 的值。
在获取根节点时，我们直接返回数组 的第一个元素。
时间复杂度方面，初始化时需要 的时间，插入节点和获取根节点的时间复杂度均为 。空间复杂度为 。其中 为树中节点的数量。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class CBTInserter:
def __init__(self, root: Optional[TreeNode]):
self.tree = []
q = deque([root])
while q:
for _ in range(len(q)):
node = q.popleft()
self.tree.append(node)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
def insert(self, val: int) -> int:
p = self.tree[(len(self.tree) - 1) // 2]
node = TreeNode(val)
self.tree.append(node)
if p.left is None:
p.left = node
else:
p.right = node
return p.val
def get_root(self) -> Optional[TreeNode]:
return self.tree[0]
# Your CBTInserter object will be instantiated and called as such:
# obj = CBTInserter(root)
# param_1 = obj.insert(val)
# param_2 = obj.get_root()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | The preprocessing is |
| 空间 | O(N_{\text{cur}}) |
面试官常问的追问
外企场景- question_mark
Candidate recognizes the need for BFS to track insertion points efficiently.
- question_mark
Candidate maintains left-to-right order at the last level, showing understanding of completeness requirements.
- question_mark
Candidate correctly handles updates to the parent queue after each insertion.
常见陷阱
外企场景- error
Failing to maintain the queue of potential parents leads to incorrect insertion order.
- error
Incorrectly updating parent nodes can violate completeness when multiple insertions occur.
- error
Re-traversing the tree for each insert increases time complexity unnecessarily.
进阶变体
外企场景- arrow_right_alt
Implement a Complete Binary Tree Inserter supporting deletion while maintaining completeness.
- arrow_right_alt
Design a variant where insertions must also balance the tree height as much as possible.
- arrow_right_alt
Extend to allow batch insertions of multiple values while preserving BFS order and completeness.