思路：完全二叉树只有最后一层是不满的，通过层序遍历就能找到应该插入的节点位置的父节点，然后将新节点插到该父节点下面即可。

class CBTInserter {
private:
    TreeNode* root;
    queue<TreeNode*> q;

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

        q.push(root);
        //只要当前节点存在左右子节点，它就是满的，将左右子节点入栈
        //直到遇见一个子节点不满的节点为止，此时退出循环，它就是我们要找的父节点
        while (q.front()->left != nullptr && q.front()->right != nullptr)
        {
            auto tmp = q.front();
            q.pop();
            q.push(tmp->left);
            q.push(tmp->right);
        }
    }

    int insert(int val) {
        TreeNode* parent = q.front();       //取得队首的节点，它的子节点不满
        TreeNode* node = new TreeNode(val); //创建节点

        if (parent->left == nullptr)        //若没有左子节点，就直接挂到左边
        {
            parent->left = node;
        }
        else                                //若没有右子节点，就直接挂到右边
        {
            parent->right = node;

            q.pop();                        //此时该节点已满，所以出队
            q.push(parent->left);           //它的左右子节点继续入队
            q.push(parent->right);
        }

        return parent->val;                 //返回该父节点的值
    }

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