图解LeetCode——919. 完全二叉树插入器（难度：中等）

一、题目

完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。设计一种算法，将一个新节点插入到一个完整的二叉树中，并在插入后保持其完整。

实现 CBTInserter 类:

• CBTInserter(TreeNode root) 使用头节点为 root 的给定树初始化该数据结构；
• CBTInserter.insert(int v) 向树中插入一个值为 Node.val == val 的新节点 TreeNode。使树保持完全二叉树的状态，并返回插入节点 TreeNode 的父节点的值；
• CBTInserter.get_root() 将返回树的头节点。

二、示例

2.1> 示例 1：

【输入】
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
【输出】
[null, 1, 2, [1, 2, 3, 4]]
【解释】
CBTInserter cBTInserter = new CBTInserter([1, 2]);
cBTInserter.insert(3); // 返回 1
cBTInserter.insert(4); // 返回 2
cBTInserter.get_root(); // 返回 [1, 2, 3, 4]

提示：

• 树中节点数量范围为 [1, 1000]
• 0 <= Node.val <= 5000
• root 是完全二叉树
• 0 <= val <= 5000
• 每个测试用例最多调用 insert 和 get_root 操作 10^4 次

三、解题思路

3.1> 广度优先+队列

首先，根据题目要求，先按照每层去添加数据，在同一层中，从左到右去添加节点。那么我们可以通过队列（queue）来执行广度优先遍历每一层的节点，在遍历过程中，再将左节点为空或者右节点为空的节点，放入的另一个队列（queueInsertNode）中，用于后续的insert操作。如下图所示：

当我们需要插入新的节点的时候，首先，将创建的新节点放入到queueInsertNode队列中，用于后续新节点的添加。其次，通过调用peek()方法获取队列头元素，但并不会从队列中删除该元素。获得头元素之后，将新节点放入该节点的左侧或者右侧，如果是放入右侧，则说明该头元素的左右叶子节点都已经存在了，那么就通过调用poll()方法将该元素“踢出”队列。具体操作如下图所示：

四、代码实现

4.1> 广度优先+队列

public class CBTInserter {
    private Queue<TreeNode> queueInsertNode;
    private TreeNode root;

    public CBTInserter(TreeNode root) {
        this.root = root;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queueInsertNode = new ArrayDeque<>();
        queue.offer(root);
        TreeNode node;
        while (!queue.isEmpty()) { // 广度优先遍历
            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) {
                queueInsertNode.offer(node);
            }
        }
    }

    public int insert(int val) {
        TreeNode newNode = new TreeNode(val);
        TreeNode node = queueInsertNode.peek();
        if (node.left == null) {
            node.left = newNode;
        } else if (node.right == null) {
            node.right = newNode;
            queueInsertNode.poll();
        }
        queueInsertNode.offer(newNode);
        return node.val;
    }

    public TreeNode get_root() {
        return root;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的点赞&分享。

更多技术干货，欢迎大家关注公众号@爪哇缪斯「干货分享，每天更新」

往期推荐

图解LeetCode——731. 我的日程安排表 II（难度：中等）https://mp.csdn.net/mp_blog/creation/editor/125884328图解LeetCode——3. 无重复字符的最长子串（难度：中等）https://mp.csdn.net/mp_blog/creation/editor/125857066LeetCode精讲——21. 合并两个有序链表（难度：简单）https://mp.csdn.net/mp_blog/creation/editor/125840103LeetCode精讲——565. 数组嵌套（难度：中等）https://mp.csdn.net/mp_blog/creation/editor/125831251

题目来源：力扣（LeetCode）