完全二叉树插入器

难度: Medium

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

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

实现 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 操作 10⁴ 次

Submission

运行时间: 39 ms

内存: 17.0 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class CBTInserter:
    def __init__(self, root: Optional[TreeNode]):
        self.root = root
        self.nodes = self._get_nodes(root)

    def _get_nodes(self, root):
        # Perform a level order traversal to get all nodes in the tree
        nodes = []
        queue = [root]
        while queue:
            node = queue.pop(0)
            nodes.append(node)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return nodes

    def insert(self, val: int) -> int:
        # Create a new node with the given value
        new_node = TreeNode(val)
        
        # Find the parent node and insert the new node as its left or right child
        parent = self.nodes[(len(self.nodes) - 1) // 2]
        if not parent.left:
            parent.left = new_node
        else:
            parent.right = new_node
        
        # Update the nodes list
        self.nodes.append(new_node)
        
        # Return the parent node's value
        return parent.val

    def get_root(self) -> Optional[TreeNode]:
        return self.root

Explain

这个题解的思路是使用层序遍历来存储树中的所有节点，这样可以轻松地找到新节点的父节点。对于插入操作，根据完全二叉树的性质，新节点应该被添加为当前最后一个节点的左孩子（如果没有左孩子的话）或者右孩子（如果左孩子已经存在）。我们可以通过当前节点总数来快速定位新节点的父节点。

时间复杂度: 构造函数的时间复杂度为 O(n)，插入操作的时间复杂度为 O(1)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class CBTInserter:
    def __init__(self, root: Optional[TreeNode]):
        self.root = root
        self.nodes = self._get_nodes(root)

    def _get_nodes(self, root):
        # Perform a level order traversal to get all nodes in the tree
        nodes = []
        queue = [root]
        while queue:
            node = queue.pop(0)
            nodes.append(node)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return nodes

    def insert(self, val: int) -> int:
        # Create a new node with the given value
        new_node = TreeNode(val)
        
        # Find the parent node and insert the new node as its left or right child
        parent = self.nodes[(len(self.nodes) - 1) // 2]
        if not parent.left:
            parent.left = new_node
        else:
            parent.right = new_node
        
        # Update the nodes list
        self.nodes.append(new_node)
        
        # Return the parent node's value
        return parent.val

    def get_root(self) -> Optional[TreeNode]:
        return self.root

Explore

是的，在CBTInserter的初始化过程中使用层序遍历确实意味着每个节点都被访问一次。这种方法的时间复杂度为O(n)，其中n是树中的节点总数。目前，对于完全二叉树而言，层序遍历是一种有效且直观的方式来获取所有节点，因为它能保证节点按照从上到下、从左到右的顺序被访问。没有明显更高效的通用方法来初始化节点列表，因为任何遍历完全二叉树的方法都需要访问树中的每个节点。

这种计算方式基于完全二叉树的性质，其中节点以层序方式填充。在层序列表中，对于任何节点i，其左孩子的索引为`2*i + 1`，右孩子的索引为`2*i + 2`。因此，对于节点列表中的第n个新插入的节点（从0开始索引），其父节点的索引应为`(n-1)//2`。这种计算方式利用了整数除法的特性，确保无论n是奇数还是偶数，都能正确返回其父节点的索引。

是的，这种插入方式符合完全二叉树的定义。完全二叉树要求除最后一层外，其他每层节点都是满的，并且最后一层的节点都尽可能地靠左排列。在`insert`方法中，新节点总是尝试先填充左孩子的位置，如果左孩子已存在，则填充右孩子的位置。这确保了节点总是按照从左到右的顺序添加，符合完全二叉树的特性。

在当前的实现中，如果根节点`root`为None，CBTInserter类的初始化可能会遇到问题，因为类中的代码假设了根节点至少存在一个有效的节点。如果传入`None`，则在尝试将其加入队列时会引发异常。因此，为了正确处理空树的情况，初始化方法中应该添加对根节点是否为`None`的检查，如果是，则应适当初始化树或返回错误/异常。