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

约 5 分钟
文章信息 5 个分类 5 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
树 广度优先搜索 二叉树 LCR 设计

题目描述

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

image-20260928235748376

image-20260928235748377

题意分析

用一棵非空完全二叉树初始化插入器。每次插入新节点后仍须保持完全二叉树，并返回新节点父节点的值；get_root 返回树根。

完全二叉树按从上到下、从左到右填充节点，所以下一个插入位置唯一。可以先保存层序编号，之后直接计算父节点位置，无需每次重新遍历。

解法：层序编号定位插入父节点

核心思路

[!blue]

将节点按层序放入数组 tree，下标从 $0$ 开始。完全二叉树的编号没有空洞，下标为 i 的节点，其左右孩子编号分别为 2*i + 1、2*i + 2；反过来，非根节点的父亲编号为 (i - 1) / 2，使用整数除法。

插入前共有 n 个节点时，已有编号恰好为 $0$ 到 $n-1$，新节点只能追加到编号 n。因此父节点就是 tree[(n - 1) / 2]，这里的 n 必须取追加前的数组长度。

所有更早编号都已存在，新位置的父节点不可能已经拥有两个孩子。若左孩子为空，就先补左孩子；否则左孩子已经存在，本次补右孩子。按这个顺序填入下一个编号，既不会留下空洞，也不会覆盖已有孩子。

数组保存的是节点引用。将新节点追加到数组后，再修改父节点的孩子指针，真实树与编号数组便同时更新。插入只发生在末尾，tree[0] 始终是原根，返回它就能获得包含所有新增节点的树。

解题步骤

  1. 构造时做一次 BFS，先左后右加入孩子，把节点按层序依次保存到 tree。
  2. 插入前读取当前节点数，计算父节点下标 (n - 1) / 2。
  3. 创建新节点并追加到数组，根据父节点是否缺左孩子决定连接方向。
  4. 返回父节点的值；get_root 直接返回数组首个节点。

代码实现

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 均摊为 $O(1)$，数组偶尔需要扩容；get_root 为 $O(1)$。
  • 空间复杂度：$O(n+m)$，其中 $n$ 为初始节点数、$m$ 为插入次数。数组为每个节点保存引用，构造期的 BFS 队列也不超过这个量级。

关键点总结

[!green]

  • 完全二叉树的层序编号连续，数组下标才能直接表示父子关系。
  • 先用追加前的长度定位父节点，再添加新节点。
  • 数组引用和父子指针都要更新，才能同时支持后续插入和返回整棵树。

易错点总结

[!yellow]

  • 构造时使用前序或中序保存节点，会使数组下标与层序编号不一致。
  • 用追加后的节点数计算父节点，可能定位到错误位置。
  • 缺左孩子时必须先补左孩子，不能留下左空右有的结构。
  • 只追加数组而不连接父节点，get_root 返回的树不会包含新节点。

相似题目

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