【leetcode】将二叉搜索树变平衡
目前是二叉搜索树二叉搜索树的性质是左子树根右子树如果想要保持好大小关系用中序遍历存储中序遍历左子树-根-右子树得到整个树的数值构成的列表然后用二分法递归求根保证平衡class Solution: def balanceBST(self, root: TreeNode) - TreeNode: # 第一步中序遍历将树“压扁”成有序数组 nums [] def inorder(node): if not node: return inorder(node.left) nums.append(node.val) inorder(node.right) inorder(root) # 第二步分治法将有序数组“提”成平衡树 def build(left, right): # Base Case: 只有当区间不合法左边跑到右边去了才返回 None # 这比在调用前检查 left mid-1 要优雅得多 if left right: return None # 1. 找中间点作为根 mid (left right) // 2 root TreeNode(nums[mid]) # 2. 递归构建左右子树 # 这里的逻辑是既然我是根那我的左孩子就是左边那半段的根... root.left build(left, mid - 1) root.right build(mid 1, right) return root # 这里的入口就是整个数组范围 return build(0, len(nums) - 1)
