题目描述

完全二叉树是每一层（除最后一层外）都是完全填充（即，结点数达到最大）的，并且所有的结点都尽可能地集中在左侧。

设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：

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

样例

输入：
["CBTInserter","insert","get_root"],
[[[1]],[2],[]]

输出：[null,1,[1,2]]

输入：
["CBTInserter","insert","insert","get_root"],
[[[1,2,3,4,5,6]],[7],[8],[]]

输出：[null,3,4,[1,2,3,4,5,6,7,8]]

注意

• 最初给定的树是完全二叉树，且包含 1 到 1000 个结点。
• 每个测试用例最多调用 CBTInserter.insert 操作 10000 次。
• 给定结点或插入结点的每个值都在 0 到 5000 之间。

算法

(队列) $O(n)$ / $O(1)$

1. 定义队列 curNodes，队头为下一次需要插入的结点的父结点。
2. 通过 bfs 在构造函数中初始化这个队列，即按顺序入队某个儿子为空的结点。
3. 当插入数字时，取出 curNodes 的队头结点，如果该结点左儿子为空，则插入新结点到左儿子上；否则插入到右儿子上，该结点出队。新结点入队。

时间复杂度

• 构造函数中每个结点仅遍历一次，故初始化时间复杂度为 $O(n)$
• 插入时，由于每个新结点在 curNodes 中出现一次，故插入的均摊时间复杂度为 $O(1)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class CBTInserter {
public:
    TreeNode *root;
    queue<TreeNode*> curNodes;

    CBTInserter(TreeNode* root) {
        this -> root = root;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            TreeNode *cur = q.front();
            q.pop();
            if (cur -> left == nullptr || cur -> right == nullptr)
                curNodes.push(cur);

            if (cur -> left != nullptr)
                q.push(cur -> left);

            if (cur -> right != nullptr)
                q.push(cur -> right);
        }
    }

    int insert(int v) {
        TreeNode *cur = curNodes.front();
        if (cur -> left == nullptr) {
            cur -> left = new TreeNode(v);
            curNodes.push(cur -> left);
        }
        else if (cur -> right == nullptr) {
            cur -> right = new TreeNode(v);
            curNodes.push(cur -> right);
            curNodes.pop();
        }

        return cur -> val;
    }

    TreeNode* get_root() {
        return root;
    }
};

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter* obj = new CBTInserter(root);
 * int param_1 = obj->insert(v);
 * TreeNode* param_2 = obj->get_root();
 */