LeetCode 919. 完全二叉树插入器

2020-09-08 HGNULB 约 11 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 919. 完全二叉树插入器

题意分析

这是一道设计题。给定一棵完全二叉树作为初始状态，实现三个接口：构造函数接收根节点；insert(v) 插入一个值为 v 的新节点，插入后整棵树必须仍然是完全二叉树，并返回新节点父节点的值；get_root() 返回根节点。

关键在于「完全二叉树」这个约束把插入位置唯一确定了。完全二叉树的定义是：除最后一层外每层都填满，且最后一层的节点全部靠左连续排列。因此新节点只能挂在层序遍历中「第一个空缺」的位置——要么是某个只有左孩子的节点的右孩子位，要么是最后一层填满后、下一层最左边的位置。没有任何选择余地，这题不是算法题而是状态维护题。

设计题要看调用频次：insert 最多被调用 $10^4$ 次，初始树也最多 1000 个节点。如果每次插入都重新 BFS 找空位，单次是 $O(n)$，总共 $O(n \cdot q)$，在这个规模下勉强能过但明显笨拙。题目真正想考的是：能否让 insert 做到均摊 $O(1)$。

于是问题变成：需要维护什么状态，才能一步找到插入位置？答案是「按层序排列的、还没满两个孩子的节点序列」——只要队首始终是下一个待填充的父节点，插入就退化成一次指针赋值。

边界：初始树保证非空，所以不必处理空根；初始树可能只有根节点（此时根就是唯一候选）；每次插入后新节点自己也成为未来的候选父节点。

解法：BFS 队列维护候选父节点

核心思路

先看朴素做法：每次 insert 都从根做一次层序遍历，找到第一个 left 或 right 为空的节点挂上去。正确，但每次插入都要重新扫描整棵树，$10^4$ 次调用叠加起来是上亿次节点访问，而且大量工作是重复的——上一次找到的空位，这一次几乎还在同一个地方。

瓶颈很明确：每次都从头重新寻找，但插入位置其实是单调向后推进的。层序遍历里的空位只会往右、往下走，永远不会回头。既然如此，就把「还有空位的节点」按层序顺序预先排好，用队列保存，每次直接取队首。

不变量：队列 candidates 中的节点，按层序从前到后排列，且恰好是当前树中所有「孩子没满两个」的节点。队首就是下一次插入时的父节点。

为什么这个不变量能被维持？因为完全二叉树的填充顺序与层序遍历顺序完全一致。构造时做一次 BFS，凡是 left 或 right 为空的节点按访问顺序入队，队列自然就按层序排好了。之后每次插入：新节点挂到队首节点上，若队首的左孩子位空就填左（此时它还差一个右孩子，仍是候选，不出队）；若左孩子已有就填右，填完它两个孩子都满了，出队。新节点本身还没有任何孩子，必然是候选，追加到队尾。

队尾追加与层序顺序一致吗？是的。新节点是当前层序中最后一个节点，它在候选序列里也理应排最后——队列的先进先出语义与完全二叉树的填充顺序天然吻合，这正是选队列而不是栈或堆的原因。

还有一个可选的优化视角：完全二叉树可以用数组表示，下标 i 的父节点是 (i-1)/2，插入第 k 个节点时父节点下标直接算出来。这个思路在纯数值场景下更快，但题目要求维护真实的 TreeNode 结构并返回根，还是队列版更贴合接口。

解题步骤

构造函数里做一次完整 BFS：从根出发逐层访问，非空孩子入遍历队列。这一趟的作用是把初始树里所有候选父节点按层序收集起来，是后续所有 $O(1)$ 插入的前提。

入队条件是 node.left == null || node.right == null：只要还缺至少一个孩子就是候选。注意判断要在孩子入队之后做（或者说与之无关），因为它检查的是当前节点自身的空位，而不是要不要继续遍历。

insert 先取队首而不弹出：parent = candidates.peek()。队首是层序中第一个有空位的节点，它就是唯一合法的父节点。先看不弹，是因为填左孩子时它还要继续留在队里等右孩子。

parent.left == null 时填左，不出队：这个节点还差一个右孩子，下一次插入仍然轮到它。这是本题最容易写错的分支——顺手 poll() 会让右孩子位永远空着，树不再是完全二叉树。

否则填右并出队：右孩子一填，parent 的两个孩子都满了，不再是候选，必须 poll() 掉，否则下一次 peek() 还会取到它，导致覆盖已有孩子。

新节点入队尾：candidates.offer(child)。它没有孩子，是层序上最靠后的候选，放队尾正合适。

返回 parent.val：题目要求返回父节点的值，不是新节点的值，也不是节点对象。

get_root() 直接返回构造时保存的根：插入只在下方挂节点，根引用从头到尾不变，用 final / 只读字段保存即可。

以初始树 [1, 2, 3, 4]（根 1，左孩子 2、右孩子 3，2 的左孩子 4）走一遍。

构造阶段：BFS 依次访问 1、2、3、4。节点 1 左右孩子都有，不入候选；节点 2 只有左孩子 4，缺右孩子，入候选；节点 3 没有孩子，入候选；节点 4 没有孩子，入候选。candidates = [2, 3, 4]。

第一次 insert(5)：队首是 2，2.left = 4 非空，走右分支，2.right = 5，节点 2 孩子已满，出队。新节点 5 入队尾。candidates = [3, 4, 5]，返回 2。此时树为 [1,2,3,4,5]，第二层填满、第三层有 4 和 5 靠左排列，仍是完全二叉树。

第二次 insert(6)：队首是 3，3.left 为空，走左分支，3.left = 6，节点 3 还缺右孩子，不出队。新节点 6 入队尾。candidates = [3, 4, 5, 6]，返回 3。树为 [1,2,3,4,5,6]。

第三次 insert(7)：队首仍是 3，3.left = 6 非空，走右分支，3.right = 7，节点 3 满了，出队。7 入队尾。candidates = [4, 5, 6, 7]，返回 3。树为 [1,2,3,4,5,6,7]，恰好是一棵满二叉树。

第四次 insert(8)：队首是 4，4.left 为空，填左，不出队，8 入队尾，返回 4。新的一层从最左边开始填，完全二叉树的性质依然成立。

对照一下写错的情形：如果第二次插入时填完左孩子就把 3 出队，第三次插入的队首会变成 4，节点 8 会挂到 4 的左边，而 3.right 永远空着——树的第三层出现了空洞，不再是完全二叉树。

代码实现

class CBTInserter {
    private final TreeNode root;
    private final ArrayDeque<TreeNode> candidates = new ArrayDeque<>();

    public CBTInserter(TreeNode root) {
        this.root = root;
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (node.left == null || node.right == null) {
                candidates.offer(node);
            }
        }
    }

    public int insert(int val) {
        TreeNode parent = candidates.peek();
        TreeNode child = new TreeNode(val);
        if (parent.left == null) {
            parent.left = child;
        } else {
            parent.right = child;
            candidates.poll();
        }
        candidates.offer(child);
        return parent.val;
    }

    public TreeNode get_root() {
        return root;
    }
}

type CBTInserter struct {
    root       *TreeNode
    candidates []*TreeNode
}

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

func (c *CBTInserter) Insert(val int) int {
    parent := c.candidates[0]
    child := &TreeNode{Val: val}
    if parent.Left == nil {
        parent.Left = child
    } else {
        parent.Right = child
        c.candidates = c.candidates[1:]
    }
    c.candidates = append(c.candidates, child)
    return parent.Val
}

func (c *CBTInserter) Get_root() *TreeNode {
    return c.root
}

复杂度分析

时间复杂度：构造函数 $O(n)$，一次 BFS 访问全部 $n$ 个节点；insert 与 get_root 均为 $O(1)$，只做一次队首查看、常数次指针赋值和一次入队。所有工作都在构造时一次付清，之后每次插入不再扫描任何子树。

空间复杂度：$O(n)$。candidates 最多同时保存约一半的节点（最后一层加上倒数第二层的部分节点）；构造时的临时 BFS 队列在返回后即可回收，峰值仍是 $O(n)$。

关键点总结

完全二叉树的插入位置由定义唯一确定，没有选择空间——先确认这一点，题目就从「怎么插」变成「怎么快速找到那个唯一位置」。

设计题的核心是选对要维护的状态。这里维护「按层序排列的未满节点队列」，把每次 $O(n)$ 的查找压成 $O(1)$ 的取队首，代价只是构造时的一次 BFS。

队列的先进先出语义与完全二叉树的层序填充顺序天然一致，所以新节点追加到队尾就自动排在正确位置，不需要任何排序或比较。

出队时机是全题的分水岭：填左孩子不出队（还差右孩子），填右孩子才出队。把这条说清楚，等于说清了整个不变量。

面试视角：先给出「每次 BFS 重新找」的可行解证明思路正确，再指出重复扫描的浪费并升级为队列版，最后主动补一句「也可以用数组下标 (i-1)/2 直接算父节点」，三层递进是这题的满分答法。

根引用在整个生命周期里不变，用只读字段保存即可；get_root 不需要任何计算，这也是「状态维护到位」的副产品。

易错点总结

填完左孩子就把队首出队：初始树 [1,2,3] 上连续 insert(4)、insert(5)，第二次会把 5 挂到节点 3 的左边，而 2.right 永远空缺，树的最后一层出现空洞，不再是完全二叉树。

填完右孩子忘记出队：同样的初始树上，节点 2 填满后仍留在队首，下一次插入会执行 2.right = 新节点，把已有的孩子直接覆盖，节点丢失。

insert 里用 poll() 代替 peek() 取父节点：填左孩子的场景下父节点被提前移除，后果同第一条。

新节点忘记入队：初始树只有根 [1] 时，insert(2) 后队列里只剩根（且根还差右孩子），再插入 insert(3) 填满根后队列变空，第四次插入 peek() 返回 null，空指针异常。

构造时入队条件写成 node.left == null && node.right == null：只把叶子当候选，初始树 [1,2,3,4] 中节点 2（有左孩子缺右孩子）不会入队，insert(5) 会跳过它去填节点 3，第三层出现空洞。

构造时用先序或后序遍历收集候选：候选顺序不再是层序，[1,2,3,4] 中可能先取到节点 4 去挂新节点，插入位置整体错乱。

返回新节点的值而不是父节点的值：insert(5) 在上例中应返回 2，返回 5 会让所有用例的返回值全错。

get_root() 里重新向上找根：TreeNode 没有父指针，无从找起；必须在构造时保存根引用。

构造时假设 root 可能为空并跳过 BFS：题目保证初始树非空，但若写了 if (root == null) return; 之后又不初始化队列，首次 insert 会在空队列上 peek() 得到 null。

Go 版用值接收者定义 Insert：func (c CBTInserter) Insert(...) 会拷贝结构体，c.candidates 的出队与追加只作用于副本，下一次调用看到的仍是旧队列，插入位置反复停在同一处。

每次 insert 都重新 BFS 找空位：功能正确但 $10^4$ 次调用叠加成 $O(nq)$，且完全浪费了「插入位置单调后移」这一性质，面试中会被直接追问。

相似题目

题目	难度	考察点
LCR 043. 完全二叉树插入器	中等	与本题同题，可直接套用
958. 二叉树的完全性检验	中等	反过来判定完全性：层序中一旦出现空位，其后不能再有非空节点
222. 完全二叉树的节点个数	中等	利用完全性把计数压到 $O(\log^2 n)$，考的是左右子树高度比较
102. 二叉树的层序遍历	中等	本题构造函数用的就是这套模板，只是额外加了候选筛选
662. 二叉树最大宽度	中等	层序时给节点编号 `2i`/`2i+1`，与完全二叉树的数组下标映射同源
297. 二叉树的序列化与反序列化	困难	同为按层序重建树，但要处理空节点占位，队列的消费顺序是关键
703. 数据流中的第 K 大元素	简单	另一道「构造时预处理、查询 $O(\log n)$」的设计题，用堆维护状态
155. 最小栈	中等	设计题的通用范式：多维护一份辅助状态，把查询从 $O(n)$ 降到 $O(1)$