原本还想说是不是要inplace
发现我想不到
我好烂
还是用个平庸的方法比较好
def balanceBST(self, root: TreeNode) -> TreeNode:
nodes = []
def dfs(root):
nonlocal nodes
if root is None:
return
dfs(root.left)
nodes.append(root.val)
dfs(root.right)
dfs(root)
def build(l,r) -> TreeNode:
if l==r:
return TreeNode(nodes[l])
elif r<l:
return None
mid = (l+r)//2
n = TreeNode(nodes[mid])
n.left = build(l,mid-1)
n.right = build(mid+1,r)
return n
return build(0, len(nodes)-1)