如何创建二叉树忘完了,直接看评论区
发现队列,想起一点
代码如下:
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]