LeetCode LCR 043. 完全二叉树插入器

2026-03-28 HGNULB 约 9 分钟

文章信息 5 个分类 5 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 043. 完全二叉树插入器

题意分析

题目目标：用一棵已有的完全二叉树初始化一个插入器，之后每次 insert(val) 把新节点挂到唯一合法的位置上使树保持完全二叉树，并返回新节点父节点的值；get_root 随时返回树根。
核心约束：完全二叉树的形状被完全钉死——除最后一层外每层都填满，最后一层的节点全部靠左连续排列，因此"下一个插入位置"在任意时刻都唯一，不存在选择空间，这意味着不需要搜索，只需要一个能直接算出该位置的编号规则。
边界处理：初始树至少有一个节点，所以父节点一定存在，不必处理空树；插入既可能补上某个节点的右孩子，也可能开启新的一层成为某节点的左孩子；插入次数可达 $10^4$ 量级，单次不能再走一遍全树。
实现取舍：真正的难点不是"怎么插"，而是"插完之后还能立刻知道下一次插哪儿"——需要一份能随插入 $O(1)$ 更新的位置信息，而不是每次现场重新扫描整棵树。

解法：广度优先搜索

核心思路

暴力做法是每次 insert 都从根开始逐层遍历，找到第一个缺孩子的节点再挂上去。单次是 $O(n)$，m 次插入总代价 $O(nm)$，在 $10^4$ 次调用下明显浪费——每次扫描出来的层序结构和上一次几乎完全一样，只多了一个节点。
瓶颈是重复遍历。观察完全二叉树最本质的性质：把节点按层序从 0 开始编号，编号为 i 的节点其左孩子编号是 2i + 1、右孩子是 2i + 2，反过来编号为 i 的节点父亲是 (i - 1) / 2（整除）。只要知道层序编号，父子关系就是纯算术，完全不需要指针跳转。
更关键的一步观察：完全二叉树的层序序列没有空洞，所以一个长度为 n 的数组就能无损表达整棵树的形状，新节点的编号必然是 n（追加在末尾），它的父亲编号必然是 (n - 1) / 2。
由此确定不变量：数组 tree 中下标 i 处存放的永远是层序编号为 i 的节点，且 tree.size() 恒等于当前节点总数。构造时用一次层序遍历把已有树摊平进数组，此后每次插入只是往数组尾部追加一个元素，不变量自动维持。至于新节点挂父亲的左边还是右边，看父亲的左孩子是否为空即可，因为完全二叉树保证左孩子先于右孩子被填充。

解题步骤

构造函数里对给定的 root 做一次层序遍历，把节点按出队顺序依次放进 tree。为什么必须是层序而不是前序或中序：只有层序遍历的访问顺序才与层序编号一致，换成其他遍历顺序，下标与编号的对应关系就断了，后面的算术公式全部失效。

遍历时先弹出节点存入数组，再依次把非空的左孩子、右孩子入队。为什么左先右后：同一层内编号从左到右递增，先左后右才能保证出队顺序与编号顺序一致。

insert(val) 先取 p = tree.get((tree.size() - 1) / 2)。为什么是这个下标：新节点的编号等于插入前的节点总数 n，代入父亲公式 (i - 1) / 2 得到 (n - 1) / 2，而 tree.size() 此刻正好是 n。

新建节点后先 tree.add(node) 维持不变量，再判断挂载方向：p.left == null 就挂左，否则挂右。为什么这个判断充分：完全二叉树中不存在"有右孩子却没有左孩子"的节点，左孩子为空就一定说明该节点当前一个孩子都没有。

返回 p.val，get_root 直接返回 tree.get(0)。为什么下标 0 永远是根：根的层序编号定义为 0，而插入只在数组尾部追加，从不改动前面的元素。

以 具体用例：初始树层序为 [1, 2, 3, 4]（根 1，左孩子 2、右孩子 3，节点 2 的左孩子 4）走一遍。构造后 tree = [1, 2, 3, 4]。第一次 insert(5)：n = 4，父亲下标 (4 - 1) / 2 = 1 即节点 2，数组追加后长度变 5，节点 2 的左孩子 4 不为空，于是 5 成为节点 2 的右孩子，返回 2。第二次 insert(6)：n = 5，父亲下标 (5 - 1) / 2 = 2 即节点 3，它的左孩子为空，于是 6 成为节点 3 的左孩子，返回 3。第三次 insert(7)：n = 6，父亲下标 (6 - 1) / 2 = 2 仍是节点 3，此时左孩子已是 6，于是 7 成为右孩子，返回 3。最终层序为 [1, 2, 3, 4, 5, 6, 7]，恰好是一棵满二叉树，形状始终合法。

代码实现

// 核心实现：广度优先搜索，维护必要状态并避免重复处理。
class CBTInserter {
    private List<TreeNode> tree = new ArrayList<>();

    public CBTInserter(TreeNode root) {
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            for (int i = q.size(); i > 0; --i) {
                TreeNode node = q.poll();
                tree.add(node);
                if (node.left != null) {
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
            }
        }
    }

    public int insert(int val) {
        TreeNode p = tree.get((tree.size() - 1) / 2);
        TreeNode node = new TreeNode(val);
        tree.add(node);
        if (p.left == null) {
            p.left = node;
        } else {
            p.right = node;
        }
        return p.val;
    }

    public TreeNode get_root() {
        return tree.get(0);
    }
}

// 核心实现：广度优先搜索，维护必要状态并避免重复处理。
type CBTInserter struct {
    tree []*TreeNode
}

func Constructor(root *TreeNode) CBTInserter {
    q := []*TreeNode{root}
    tree := []*TreeNode{}
    for len(q) > 0 {
        for i := len(q); i > 0; i-- {
            node := q[0]
            q = q[1:]
            tree = append(tree, node)
            if node.Left != nil {
                q = append(q, node.Left)
            }
            if node.Right != nil {
                q = append(q, node.Right)
            }
        }
    }
    return CBTInserter{tree}
}

func (this *CBTInserter) Insert(val int) int {
    p := this.tree[(len(this.tree)-1)/2]
    node := &TreeNode{val, nil, nil}
    this.tree = append(this.tree, node)
    if p.Left == nil {
        p.Left = node
    } else {
        p.Right = node
    }
    return p.Val
}

func (this *CBTInserter) Get_root() *TreeNode {
    return this.tree[0]
}

复杂度分析

时间复杂度：构造 $O(n)$，单次 insert 与 get_root 均为 $O(1)$。凭什么：构造时每个节点恰好入队出队一次；插入只做一次下标计算、一次数组追加和一次指针赋值，追加在均摊意义下是常数。

空间复杂度：$O(n + m)$，n 为初始节点数、m 为插入次数。凭什么：数组为每个节点保存一个引用，队列在构造期最多容纳一层的节点数，两者都不超过总节点数。

关键点总结

完全二叉树与数组一一对应：层序编号 i 的左右孩子是 2i + 1 与 2i + 2，父亲是 (i - 1) / 2。把树摊平成数组，指针问题就变成算术问题，这既是堆的实现原理，也是本题的全部内核。

摊平的前提是"层序无空洞"，由完全二叉树的定义保证；若树可能残缺，同样的下标公式立刻失效，必须改成显式记录空位。

设计类题目的通用思路是先问清"哪些操作会被反复调用"，再为这些操作预建一份能 $O(1)$ 更新的索引，而不是每次现场计算。

"左孩子为空就挂左"之所以成立，靠的是完全二叉树不允许出现只有右孩子的节点，这类由题目性质兜底的简化一定要讲出理由，而不是当成显然。

面试视角：加分项是主动提出"其实不必存下全部节点，只需要一个从待插入位置的父亲开始的队列，把已经填满两个孩子的节点弹掉"，把空间降到 $O(w)$（w 为最后一层宽度）；能同时讲清数组解法和队列解法，才算真正吃透形状约束。

易错点总结

错误写法：父亲下标写成 tree.size() / 2 → 初始树 [1, 2, 3, 4] 插入时正确父亲下标是 1（节点 2），错误公式得 2，新节点被挂到节点 3 上，树的形状立刻破坏。

错误写法：在算父亲下标之前就执行了 tree.add(node) → 数组长度提前加一，表达式变成 n / 2，初始 [1, 2, 3, 4] 插入时父亲错取成节点 3，返回值和树形都错。

错误写法：构造时用前序遍历填充数组 → 树 [1, 2, 3, 4] 的前序序列是 1, 2, 4, 3，下标 2 处成了节点 4，此后所有父子公式全部错位。

错误写法：层序遍历时先入队右孩子再入队左孩子 → 树 [1, 2, 3] 摊平成 [1, 3, 2]，插入时算出的父亲左右颠倒，返回值与真实父节点不符。

错误写法：挂载判断写成 if (p.right == null) p.right = node; else p.left = node; → 初始树 [1, 2, 3] 插入 4 时挂成节点 2 的右孩子，节点 2 出现只有右孩子的非法形态，后续判定连锁出错。

错误写法：遍历时把 null 孩子也入队 → 出队后访问 node.left 直接空指针异常；即便加判空跳过，数组里也会插入空洞，破坏下标与编号的对应。

错误写法：get_root 返回最近一次插入用到的父节点 → 初始树只有一个节点时连续插入两次，返回的不是根而是中间节点，判题拿到的整棵树都对不上。

错误写法：Go 中方法用值接收者 func (this CBTInserter) Insert(val int) int → 追加只作用在结构体副本上，第二次插入时长度仍是初始值，父亲下标反复取到同一个节点。

错误写法：每次 insert 都重新做一遍层序遍历定位插入点 → 结果虽正确，但 $10^4$ 次插入的总代价升到 $10^8$ 级别导致超时，也丢掉了这题真正想考的编号性质。

相似题目

题目	难度	考察点
222. 完全二叉树的节点个数	中等	同样吃形状红利，但用二分判定最后一层节点的存在性
958. 二叉树的完全性检验	中等	反向判断形状：层序遇到空位后不允许再出现实节点
102. 二叉树的层序遍历	中等	层序遍历本身的分层控制写法
107. 二叉树的层序遍历 II	中等	层序结果需自底向上组织，考察结果收集顺序
297. 二叉树的序列化与反序列化	困难	一般二叉树没有形状保证，必须显式编码空位