给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。
如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 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] 也是一个可行的构造方案。
提示：
树节点的数目在 1 到 10^4 之间。
树节点的值互不相同，且在 1 到 10^5 之间。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/balance-a-binary-search-tree
python
# 1382.二叉搜索树变平衡树
# 中序递归-数组-转二叉搜索树
class Solution:
def balanceBST(self, root: TreeNode) -> TreeNode:
res = []
# 中序递归->有序树转数组
def travel(cur: TreeNode):
if not cur:
return
travel(cur.left)
res.append(cur.val)
travel(cur.right)
# 有序数组转平衡二叉树
def buildBalancedBST(nums: [int], left: int, right: int) -> TreeNode:
if left > right:
return
mid = left + int((right-left) >> 1)
root = TreeNode(nums[mid])
root.left = buildBalancedBST(nums, left, mid-1)
root.right = buildBalancedBST(nums, mid+1, right)
return root
travel(root)
return buildBalancedBST(res, 0, len(res)-1)
golang
package binaryTree
// 递归中序生成排序的数组，根据数组左闭右闭递归生成BST
func balanceBST(root *TreeNode) *TreeNode {
res := []int{}
var travel func(cur *TreeNode)
var buildBalancedBST func(nums []int, left, right int) *TreeNode
travel = func(cur *TreeNode) {
if cur == nil {
return
}
travel(cur.Left)
res = append(res, cur.Val)
travel(cur.Right)
}
buildBalancedBST = func(nums []int, left, right int) *TreeNode {
if left > right {
return
}
var mid int = left + (right - left) >> 1
root := &TreeNode{Val: nums[mid]}
root.Left = buildBalancedBST(nums, left, mid-1)
root.Right = buildBalancedBST(nums, mid+1, right)
return root
}
travel(root)
return buildBalancedBST(res, 0, len(res)-1)
}