919.完全二叉树插入器

【LetMeFly】919.完全二叉树插入器：完全二叉树的数组表示

力扣题目链接：https://leetcode.cn/problems/complete-binary-tree-inserter/

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

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

实现 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 次

方法一：用数组存储完全二叉树

完全二叉树具有以下性质：

如果根节点从1开始按层次遍历的方式进行编号，那么$父节点的编号=\lfloor \frac{子节点的编号}{2}\rfloor$

因此，我们可以用数组存放完全二叉树的节点，这样在添加新的节点时，直接将新节点追加到数组尾部，就可以很容易地得到新节点的父节点$O(1)$。

之后，把父节点的子节点指向新节点即可。

• 时间复杂度$O(n)$，其中$n$是初始二叉树的节点个数
• 空间复杂度$O(m)$，其中$m$是最终二叉树的节点个数

AC代码

C++

class CBTInserter {
private:
    vector<TreeNode*> a;
public:
    CBTInserter(TreeNode* root) {  // 初始二叉树，按照层次遍历的方式存入数组
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
            TreeNode* p = q.front();
            q.pop();
            a.push_back(p);
            if (p->left)
                q.push(p->left);
            if (p->right)
                q.push(p->right);
        }
    }
    
    int insert(int val) {
        TreeNode* thisNode = new TreeNode(val);  // 新节点
        a.push_back(thisNode);
        int th = a.size();  // 新节点的编号
        TreeNode* father = a[th / 2 - 1];  // 父节点的编号 = 新节点的编号 / 2  ；-1是因为数组中下标从0开始而二叉树节点从1开始编号
        if (th % 2) {  // 奇数说明是左节点
            father->right = thisNode;
        }
        else {
            father->left = thisNode;
        }
        return father->val;
    }
    
    TreeNode* get_root() {
        return a[0];  // 根就是数组中的第一个节点
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/125974862