leetcode-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]

解题

方法一：双队列—O(1)复杂度插入

如果每次插入的时候都进行层序遍历，那么如果在插入情况比较多的时候，效率会很低。
如果能直接从队列中取出节点，然后插入，那么就会快很多。

由于是完美二叉树，被插入的节点，只可能是2种状态

1. 没有左、右子节点， 这种情况下后续是先插入左节点
2. 有左子节点，没右子节点，这种情况下，插入右节点

初始化的时候将情况1，存储在q_L队列中，将情况2，存储在q_R队列中。

因此可以通过层序遍历，初始化q_L,q_R队列
由于完全二叉树的特性，插入的时候，优先从q_R队列中取值。

/** * 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 {
    
public:
    TreeNode* root;
    queue<TreeNode*> q_L;//存放没有左右孩子的节点
    queue<TreeNode*> q_R;//存放没有右孩子的节点

    CBTInserter(TreeNode* root) {
    //目的是为了初始化q_L和q_R队列
        this->root=root;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
    
            TreeNode* cur=q.front();
            q.pop();
            if(!cur->left&&!cur->right) q_L.push(cur);
            if(cur->left&&!cur->right) q_R.push(cur);

            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }
    }
    
    int insert(int val) {
    
        if(!q_R.empty()){
    //优先取仅没有右孩子的节点(因为完全二叉树的特点)
            TreeNode* cur=q_R.front();
            q_R.pop();
            cur->right=new TreeNode(val);
            q_L.push(cur->right);
            return cur->val;
        }
        else{
    //取没有左右孩子的节点
            TreeNode* cur=q_L.front();
            q_L.pop();
            cur->left=new TreeNode(val);
            q_R.push(cur);
            q_L.push(cur->left);
            return cur->val;
        }
    }

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

方法二：插入时–层序遍历

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