如何创建二叉树忘完了,直接看评论区
发现队列,想起一点

代码如下:

class CBTInserter:
    def __init__(self, root: TreeNode):
        self.treeList = []
        self.treeList.append(root)

        n = root        # 给的 root 可能有子树,所以需要将所有结点存入 treeList
        i = 0           # 我比较懒,直接用列表全存了
        while n:
            if n.left:
                self.treeList.append(n.left)
            if n.right:
                self.treeList.append(n.right)

            if i + 1 < len(self.treeList):
                i += 1
                n = self.treeList[i]
            else:
                n = None

    def insert(self, val: int) -> int:      # 用列表的好处就是找父结点方便
        node = TreeNode(val)
        n = len(self.treeList) - 1
        father = self.treeList[n // 2]
        if not father.left:
            father.left = node
        else:
            father.right = node

        self.treeList.append(node)
        
        return father.val

    def get_root(self) -> TreeNode:         # 树的头结点就是 treeList 的第 0 个元素
        return self.treeList[0]