【919. 完全二叉树插入器】

来源：力扣（LeetCode）

描述：

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

设计一种算法，将一个新节点插入到一个完整的二叉树中，并在插入后保持其完整。

实现 CBTInserter 类:

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

示例 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⁴ 次

方法一：队列

思路与算法

对于一棵完全二叉树而言，其除了最后一层之外都是完全填充的，并且最后一层的节点全部在最左侧。那么，只有倒数第二层（如果存在）最右侧的若干个节点，以及最后一层的全部节点可以再添加子节点，其余的节点都已经拥有两个子节点。

因此，我们可以使用一个队列存储上述提到的这些可以添加子节点的节点。队列中的存储顺序为：首先 「从左往右」 存储倒数第二层最右侧的节点，再「从左往右」存储最后一层的全部节点。这一步可以使用广度优先搜索来完成，因为广度优先搜索就是按照层优先进行遍历的。

随后，当我们每次调用 insert(val) 时，我们就创建出一个节点 child，并将它最为队列的队首节点的子节点。在这之后，我们需要把 child 加入队尾，并且如果对队首节点已经有两个子节点，我们需要将其从队列中移除。

代码：

class CBTInserter {
    
public:
    CBTInserter(TreeNode* root) {
    
        this->root = root;

        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
    
            TreeNode* node = q.front();
            q.pop();
            if (node->left) {
    
                q.push(node->left);
            }
            if (node->right) {
    
                q.push(node->right);
            }
            if (!(node->left && node->right)) {
    
                candidate.push(node);
            }
        }
    }
    
    int insert(int val) {
    
        TreeNode* child = new TreeNode(val);
        TreeNode* node = candidate.front();
        int ret = node->val;
        if (!node->left) {
    
            node->left = child;
        }
        else {
    
            node->right = child;
            candidate.pop();
        }
        candidate.push(child);
        return ret;
    }
    
    TreeNode* get_root() {
    
        return root;
    }

private:
    queue<TreeNode*> candidate;
    TreeNode* root;
};

执行用时：16 ms, 在所有 C++ 提交中击败了84.07%的用户
内存消耗：21.9 MB, 在所有 C++ 提交中击败了43.66%的用户
复杂度分析
时间复杂度：初始化 CBTInserter(root) 需要的时间为 O(n)，其中 n 是给定的初始完全二叉树的节点个数。 insert(v) 和 get_root() 的时间复杂度均为 O(1)。
空间复杂度：O(n + q)，其中 q 是 insert(v) 的调用次数。在调用了 q 次 insert(v) 后，完全二叉树中有 n + q 个节点，其中有一半的节点在队列中，需要 O(n + q) 的空间。

方法二：二进制表示

思路与算法

如果我们将完全二叉树的每个节点进行编号，其中：

• 根节点的编号为 1；

• 如果某个节点的编号为 x，那么其左子节点的编号为 2x ，右子节点的编号为 2x + 1。

代码：

class CBTInserter {
    
public:
    CBTInserter(TreeNode* root) {
    
        this->root = root;

        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
    
            ++cnt;
            TreeNode* node = q.front();
            q.pop();
            if (node->left) {
    
                q.push(node->left);
            }
            if (node->right) {
    
                q.push(node->right);
            }
        }
    }
    
    int insert(int val) {
    
        ++cnt;
        TreeNode* child = new TreeNode(val);
        TreeNode* node = root;
        int highbit = 31 - __builtin_clz(cnt);
        for (int i = highbit - 1; i >= 1; --i) {
    
            if (cnt & (1 << i)) {
    
                node = node->right;
            }
            else {
    
                node = node->left;
            }
        }
        if (cnt & 1) {
    
            node->right = child;
        }
        else {
    
            node->left = child;
        }
        return node->val;
    }
    
    TreeNode* get_root() {
    
        return root;
    }

private:
    int cnt = 0;
    TreeNode* root;
};

执行用时：16 ms, 在所有 C++ 提交中击败了84.07%的用户
内存消耗：21.6 MB, 在所有 C++ 提交中击败了98.82%的用户
复杂度分析
时间复杂度：初始化 CBTInserter(root) 需要的时间为 O(n)，其中 n 是给定的初始完全二叉树的节点个数。
空间复杂度：初始化 CBTInserter(root) 需要的空间为 O(n)。如果使用优化方法，空间可以降低到 O(logn)。其它所有函数调用都只需要 O(1) 的空间。
author：LeetCode-Solution