类中多函数填写，LeetCode919——完全二叉树插入器

题目内容

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

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

实现 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

其实如果但是说这个题目意思的话，其实还是好理解的，就是一个完全二叉树+节点的问题，但是麻烦的地方一个是二叉树的构建上，他们提供了一棵二叉树，但是我在一开始理解初始化函数功能的时候出现了偏差，以为是要我们自己构建出一个完全二叉树来，这点我尝试实现了一下，效果其实并不好。
后来看了题解的思路我才反应过来初始化函数的功能其实并没有什么明确的限制，只是为之后的函数服务的罢了。只要初始化的时候把所有叶子结点和可能存在的一个只有左节点没有右节点的节点存在队列里面。然后去一个出来连接上就是二叉树的插入了。至于返回父节点，我们找到节点的过程就输出了。
这是我第一个在力扣上做这种多个函数类型的题目，感觉还是有一些不自然，之后多练练希望可以好一些，就像昨天周赛的时候一样，遇到多个函数自己写类的题目，因为缺乏经验而无从下手，所以还是得加紧练习才行。

实现代码

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class CBTInserter {
    
private:
    TreeNode* node;
    queue<TreeNode*> link;

public:
    CBTInserter(TreeNode* root) {
    
        node=root;
        queue<TreeNode*> q;
        if(!root){
    
            node=nullptr;
        }
        q.push(root);
        while(!q.empty()){
    
            TreeNode* dian=q.front();
            q.pop();
            if(dian->left){
    
                q.push(dian->left);
            }
            if(dian->right){
    
                q.push(dian->right);
            }
            if(!dian->left||!dian->right){
    
                link.push(dian);
            }  
        }
    }
    
    int insert(int val) {
    
        TreeNode* dian=new TreeNode(val);
        TreeNode* mid=link.front();
        if(mid->left){
    
            mid->right=dian;
            link.pop();
            link.push(dian);
        }
        else{
    
            mid->left=dian;
            link.push(dian);
        }
        return mid->val;
    }
    
    TreeNode* get_root() {
    
        return node;
    }
};

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