原本還想說是不是要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)