题目
完全二叉树 是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。
设计一种算法，将一个新节点插入到一个完整的二叉树中，并在插入后保持其完整。
实现 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 次
思路
- 使用队列模拟，遍历二叉树的所有节点，发现左孩子或者右孩子为空的节点即记录，标记该节点。就是代码中get_temp()方法
- 初始化：记录根节点，以便get_root()方法直接返回， 调用get_temp()方法获得首个标记节点
- 将给定值插入到标记节点中，并重置该标记节点即可
题解
from collections import deque class CBTInserter: # 初始化 def __init__(self, root: TreeNode): self.root = root self.temp = self.get_temp(root) def insert(self, val: int) -> int: # 构造子节点，插入到标记节点中 if self.temp.left: self.temp.right = TreeNode(val) else: self.temp.left = TreeNode(val) # 记录标记节点的值，在后面返回 value = self.temp.val # 重置标记节点 self.temp = self.get_temp(self.root) return value def get_root(self) -> TreeNode: return self.root # 寻找子节点为空的节点 def get_temp(self, root): # 队列 res = deque() res.append(root) while res: index = res.popleft() if index.left: res.append(index.left) # 左孩子为空，直接返回该节点 else: return index if index.right: res.append(index.right) # 右孩子为空，直接返回该节点 else: return index return None
