剑指 Offer II 043. 往完全二叉树添加节点

力扣

维护一个队列，插入二叉树的节点，根据完全二叉树的性质，不断把左右节点都存在的节点pop出来，使得队列中只存在没有左子树或右子树的节点。插入节点时，如果左子树是空，就插入左子树；如果右子树是空，就插入右子树，并把当前节点的左右子树push进队列，把当前节点pop出来。

class CBTInserter {
public:
    TreeNode* root;
    queue q;
    CBTInserter(TreeNode* root) {
        this->root = root;
        q.push(root);
        while(q.front()->left != nullptr && q.front()->right != nullptr){
            auto cur = q.front();
            q.pop();
            q.push(cur->left);
            q.push(cur->right);
        }
    }
    
    int insert(int v) {
        TreeNode* node = new TreeNode(v);
        TreeNode* cur = q.front();
        if(cur->left == nullptr){
            cur->left = node;
        }else{
            cur->right = node;
            q.pop();
            q.push(cur->left);
            q.push(cur->right);
        }
        return cur->val;
    }
    
    TreeNode* get_root() {
        return root;
    }
};