919. 完全二叉树插入器
题目：完全二叉树 是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。
设计一种算法，将一个新节点插入到一个完整的二叉树中，并在插入后保持其完整。
实现 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 操作 104 次
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/complete-binary-tree-inserter
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
提及完全二叉树就想到BFS，因为完全二叉树的构建离不开层次遍历，首先定义好存储有空位置的节点的队列以及根节点的指针，在构造函数中，将根节点指针指向根节点，接着用BFS遍历二叉树将所有满足条件的节点全部放入存储有空位置的节点的队列中，insert函数就是处理队列的头，如果为叶子，就填充左节点，否则填充完右节点后直接pop()，同时把新节点放入队列后面，get_root函数直接返回根节点指针即可。
代码：
class CBTInserter {
private:
TreeNode* node;
// 存储有空位置的节点
queue q;
public:
CBTInserter(TreeNode* root) {
node = root;
queue temp;
temp.emplace(root);
// BFS遍历二叉树
while(!temp.empty()) {
int n = temp.size();
for(int i = 0; i < n; i ++) {
TreeNode* tree = temp.front();
if(!(tree->left != nullptr && tree->right != nullptr)) {
q.emplace(tree);
}
if(tree->left != nullptr) temp.emplace(tree->left);
if(tree->right != nullptr) temp.emplace(tree->right);
temp.pop();
}
}
}
int insert(int val) {
TreeNode* tree = new TreeNode(val);
TreeNode* temp = q.front();
// 叶子节点，完全二叉树，所以判断左子树即可
if(temp->left == nullptr) {
temp->left = tree;
} else if(temp->right == nullptr) {
temp->right = tree;
q.pop();
}
q.emplace(tree);
return temp->val;
}
TreeNode* get_root() {
return node;
}
};
