难度: Medium
给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。
如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。
示例 1：
输入：root = [1,null,2,null,3,null,4,null,null] 输出：[2,1,3,null,null,null,4] 解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。
示例 2：
输入: root = [2,1,3] 输出: [2,1,3]
提示：
[1, 104] 范围内。1 <= Node.val <= 105运行时间: 312 ms
内存: 21.8 MB
# 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:
if root is None:
return
vals = []
stack = []
while root is not None or len(stack) > 0:
if root is not None:
stack.append(root)
root = root.left
else:
root = stack.pop()
vals.append(root.val)
root = root.right
return self.buildBST(vals, 0, len(vals)-1)
def buildBST(self, vals, i, j):
if i > j:
return
mid = (i + j) // 2
root = TreeNode(vals[mid])
root.left = self.buildBST(vals, i, mid-1)
root.right = self.buildBST(vals, mid+1, j)
return root
该题解的主要思路分为两个步骤： 1. 利用中序遍历将二叉搜索树转换成一个有序数组。中序遍历的顺序保证了数组的有序性，因为对于任何二叉搜索树，其中序遍历结果都是按照键值升序排列的。 2. 使用递归方法根据有序数组构建一棵平衡二叉搜索树（BST）。选取数组的中间元素作为树的根节点，然后递归地对中间元素的左半部分和右半部分执行同样的操作，分别生成左子树和右子树。这种方法可以确保新树的平衡性，因为每次都是从中间划分数组。
时间复杂度: O(n)
空间复杂度: O(n)
# 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:
# 中序遍历以获取有序数组
if root is None:
return
vals = []
stack = []
while root is not None or len(stack) > 0:
if root is not None:
stack.append(root)
root = root.left
else:
root = stack.pop()
vals.append(root.val)
root = root.right
# 通过有序数组构建平衡BST
return self.buildBST(vals, 0, len(vals)-1)
def buildBST(self, vals, i, j):
# 递归终止条件
if i > j:
return
# 选择中间元素作为根节点
mid = (i + j) // 2
root = TreeNode(vals[mid])
# 递归构建左右子树
root.left = self.buildBST(vals, i, mid-1)
root.right = self.buildBST(vals, mid+1, j)
return root
选择数组的中间元素作为根节点是为了保证构建的二叉搜索树的平衡性。这种方法可以最大程度上确保左右子树的节点数量相近，从而减小树的高度并优化搜索、插入和删除等操作的时间复杂度。如果选择非中间位置的元素作为根节点，可能会导致一边的子树节点过多，另一边过少，从而形成不平衡的二叉搜索树，影响操作的效率。
在将二叉搜索树转换成有序数组的过程中，重复元素会按照它们在树中的遍历顺序依次被添加到数组中。这种处理方式不会影响最终平衡二叉搜索树的结构，因为数组保持有序，而构建平衡二叉搜索树的算法依旧是选取中间元素作为根节点，递归地构建左右子树。重复元素的存在不改变节点的选择顺序和构建逻辑，因此生成的树依然保持平衡。
当节点总数为偶数时，选择中间任一元素作为根节点可能会导致左右子树的节点数差异最大为1。这种轻微的差异通常不会明显影响树的平衡性，因为无论选择中间的哪一个元素，构建出的二叉搜索树的高度差距极小，仍然可以认为是平衡的。在实际应用中，可以根据具体情况选择中间的哪一个元素作为根节点，以尽可能保持更好的平衡性。
题解中的方法通过选取中间元素作为根节点，理论上可以保证每次构建的子树尽可能平衡，从而使得递归深度接近O(log n)。在正常情况下，递归构建的过程应该不会出现更不平衡的情况。但是，如果输入的有序数组本身由于某些特殊原因（如多个重复值集中在数组的某一部分）导致分布极不均匀，可能会在实际构建时造成局部的不平衡。然而，这种情况在普通的二叉搜索树转换为有序数组过程中是不太可能发生的。