leetcode919. 完全二叉树插入器，队列只保存右子树为空的节点

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]

题目分析

CBTInserter 类用于在完全二叉树（CBT）中插入新节点。完全二叉树是一种特殊的二叉树，除了最后一层外，每一层都是满的，最后一层的节点都尽可能地靠左排列。

算法介绍

该类使用了一个队列 q 来存储所有右子树为空的节点。在插入新节点时，它会找到队列中的第一个节点（即队首节点），如果该节点的左子树为空，则将新节点作为其左子树；如果左子树非空但右子树为空，则将新节点作为其右子树。然后根据需要更新队列。

算法步骤

1. 初始化：在构造函数中，将根节点加入队列，然后遍历队列，确保队列只包含右子树为空的节点。
2. 插入新节点：
   • 创建新节点。
   • 检查队首节点的左子树和右子树。
   • 将新节点作为队首节点的左子树或右子树。
   • 根据需要更新队列。
3. 获取根节点：返回树的根节点。

算法流程图

具体代码

class CBTInserter {
    TreeNode *root;
    queue<TreeNode*> q;
public:
    CBTInserter(TreeNode* root) : root(root) {
        q.push(root);
        while (!q.empty()) {    // 队列只保存右子树为空的节点
            if (q.front() -> left) q.push(q.front() -> left);
            if (q.front() -> right) { q.push(q.front() -> right); q.pop(); }
            else break;   // 队首节点的右孩子为空，则停止
        }
    }
    
    int insert(int val) {
        auto node = new TreeNode(val);
        int res = q.front() -> val;
        if (!q.front() -> left) {   // 左子树为空
            q.front() -> left = node;
        } else {    // 左子树非空、右子树为空
            q.front() -> right = node;
            q.pop();    // 队首节点左右两侧均已插入、弹出队首节点
        } 
        q.push(node);
        return res;
    }
    
    TreeNode* get_root() {
        return root;
    }
};

算法分析

• 复杂度：插入操作的时间复杂度为 O(1)，因为队列的进出操作都是常数时间。
• 易错点：在更新队列时，需要确保队列只包含右子树为空的节点。
• 注意点：在插入新节点后，需要将其加入队列。

相似题目