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

Categories:

题目描述
思路分析
1. 解法一：队列维护可插入节点（推荐）
相似题目

题目描述

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

思路分析

解法一：队列维护可插入节点（推荐）

核心思路：

层序遍历初始化队列，仅保留“缺左或缺右”的节点。

插入时取队首作为父节点：优先补左子，再补右子；若右子也补完则出队。

新节点可能仍可作为父节点，将其入队。

复杂度分析：

时间复杂度：O(1)，每次插入只涉及队首节点。

空间复杂度：O(n)，队列存储部分节点。

import java.util.*;

class CBTInserter {
    private final TreeNode root;
    private final Deque<TreeNode> queue;

    public CBTInserter(TreeNode root) {
        this.root = root;
        this.queue = new ArrayDeque<>();

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

    public int insert(int val) {
        TreeNode parent = queue.peekFirst();
        TreeNode node = new TreeNode(val);

        if (parent.left == null) {
            parent.left = node;
        } else {
            parent.right = node;
            queue.pollFirst();
        }

        queue.offerLast(node);
        return parent.val;
    }

    public TreeNode get_root() {
        return root;
    }
}

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

func Constructor(root *TreeNode) CBTInserter {
    inserter := CBTInserter{root: root}

    bfs := []*TreeNode{root}
    for len(bfs) > 0 {
        node := bfs[0]
        bfs = bfs[1:]

        if node.Left != nil {
            bfs = append(bfs, node.Left)
        }
        if node.Right != nil {
            bfs = append(bfs, node.Right)
        }

        if node.Left == nil || node.Right == nil {
            inserter.queue = append(inserter.queue, node)
        }
    }

    return inserter
}

func (c *CBTInserter) Insert(val int) int {
    parent := c.queue[0]
    node := &TreeNode{Val: val}

    if parent.Left == nil {
        parent.Left = node
    } else {
        parent.Right = node
        c.queue = c.queue[1:]
    }

    c.queue = append(c.queue, node)
    return parent.Val
}

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

相似题目

题目	难度	考察点
116. 填充每个节点的下一个右侧节点指针	中等	层序遍历
117. 填充每个节点的下一个右侧节点指针 II	中等	层序遍历
199. 二叉树的右视图	中等	BFS
958. 二叉树的完全性检验	中等	完全二叉树
1161. 最大层内元素和	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/91226978