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]
提示：
- 树中节点数量范围为
[1, 1000]
0 <= Node.val <= 5000
root是完全二叉树
0 <= val <= 5000
- 每个测试用例最多调用
insert和get_root操作104次
法 1 层序遍历
思路
按照层序遍历的思想。先维护一个队列，然后维护一个 左右节点不全存在的 节点，即为插入点的父节点，当改节点的左右都插满了，则从队列中取出一个节点，做为下一个插入到的父节点。
题解
# 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: TreeNode): self.root = root # 找 第一个非 完全子树的节点 self.queue = deque() self.queue.append(root) # 一直指向待插入的节点 self.cur_parent = None cur = root while self.queue: cur = self.queue.popleft() if cur.left and cur.right: self.queue.append(cur.left) self.queue.append(cur.right) else: self.cur_parent = cur # 肯定没有右节点，左节点有无还需要判断 if cur.left: self.queue.append(cur.left) break def insert(self, val: int) -> int: # 插入点的父节点 res = self.cur_parent.val node = TreeNode(val) self.queue.append(node) if self.cur_parent.left: self.cur_parent.right = node # 改变 插入点的父节点 self.cur_parent = self.queue.popleft() else: self.cur_parent.left = node return res def get_root(self) -> TreeNode: return self.root # Your CBTInserter object will be instantiated and called as such: # obj = CBTInserter(root) # param_1 = obj.insert(val) # param_2 = obj.get_root()