LeetCode 1382. [Python] Balance a Binary Search Tree [Facebook]
原题链接
中等
作者:
徐辰潇
,
2021-02-03 11:51:49
,
所有人可见
,
阅读 339
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def balanceBST(self, root: TreeNode) -> TreeNode:
#TC: O(len(root))
#SC: O(len(root))
#First use inorder trasversal to concert original tree to list
#Then contruct the tree
List = []
def dfs(root):
if not root:
return
dfs(root.left)
List.append(root.val)
dfs(root.right)
dfs(root)
n = len(List)
dfs(root)
rootidx = List[n//2]
def ConstructTree(lower, upper):
if lower > upper:
return
rootidx = (lower + upper) // 2
Node = TreeNode(List[rootidx])
Node.left = ConstructTree(lower, rootidx-1)
Node.right = ConstructTree(rootidx+1, upper)
return Node
return ConstructTree(0, n-1)