LeetCode 919. 完全二叉树插入器

约 5 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 快手
标签
树 广度优先搜索 二叉树 设计

题目描述

✅ 919. 完全二叉树插入器

image-20260929105119158

image-20260929105119268

题意分析

初始是一棵非空完全二叉树。每次插入都要继续保持从上到下、从左到右填满的形状，并返回新节点的父节点值；get_root 返回当前树的根，根节点身份不会因插入而改变。

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

核心思路

[!blue]

完全二叉树的下一个空位，就是层序顺序中第一个尚未填上的孩子位置。如果每次插入都从根重新寻找会重复遍历，可以直接保留「按层序排列、尚未拥有两个孩子」的候选父节点队列。

构造时做一次从左到右的层序遍历，遇到左孩子或右孩子为空的节点就加入 candidates。队首因此是最浅、最靠左的未满节点，正是下次插入应选择的父节点。已填满的节点不再有插入机会，无需保留在候选队列中。

插入时取队首：若左孩子为空，先填左边，父节点还缺右孩子，继续留在队首；否则它只可能缺右孩子，填上后两个位置都满了，将父节点出队。初始树完全、每次又按这个顺序插入，所以不会出现需要先填右边的情况。

新节点没有孩子，将来也是候选父节点。它刚插入当前层序的最后位置，因此追加到队尾就能维持所有候选的层序顺序。每次只调整队首和队尾，下一次仍能直接取得正确父节点，不必重新遍历或排序。

解题步骤

  1. 构造时层序扫描，收集孩子尚未满两个的节点。
  2. 插入时取候选队首作为父节点。
  3. 左空填左，否则填右并移除已满父节点。
  4. 将新节点放入队尾，返回父节点值。

初始只有根节点时，它就是唯一候选，同样按先左后右处理。有限非空二叉树总有叶子，且每次插入都会加入新候选，所以插入时队列不会为空。get_root 直接返回保存的根指针，即可看到已经插入的新节点。

代码实现

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)$；insert 均摊 $O(1)$，单次扩容最坏可能 $O(N)$，N 为当前节点数；get_root 为 $O(1)$。
  • 空间复杂度：$O(n+q)$，n 为初始节点数，q 为新增节点数，候选队列随当前树增长。

关键点总结

[!green]

  • 队首是层序最早的未满节点。
  • 填左不出队，填右才出队。
  • 新节点也要登记为未来的候选父节点。

易错点总结

[!yellow]

  • 填左后立即出队：右侧空位会被跳过。
  • 填右后不出队：下一次可能覆盖已有右孩子。
  • 只收集叶子作为候选：遗漏已有左孩子但缺右孩子的节点。
  • 新节点不入队：下一层没有可用父节点记录。

相似题目

题目 难度 关联与区别
958. 二叉树的完全性检验 中等 同样利用完全二叉树层序空位必须集中在末尾的性质，原题验证结构，本题维护下一插入位置。
102. 二叉树的层序遍历 中等 层序遍历可建立尚未满的父节点队列，让每次插入无需重新遍历。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2020/43341833
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！