树，返回一个节点值相同的平衡二叉搜索树。二叉搜索树是平衡的当且仅当每个节点的两个子树的深度相差不超过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]也是正确的。约束条件：树中的节点数在1到10^4之间。树节点将在1到10^5之间有不同的值。问题是给你一个二叉搜索树。请返回一个平衡的二叉搜索树。新生成的树应该和原来的树有相同的节点值。如果在一棵二叉搜索树中，每个节点的两个子树的高度差不超过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之间。二叉树的思想是先将二叉查找树转成数组，然后一分为二建树。Python3代码#定义二叉树节点。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=NonefromtypingimportListclass解决方案：defbalanceBST(self,root:TreeNode)->TreeNode:ifnotroot:returnreturnself.build(self.dfs(root))#将二叉搜索树转换为数组defdfs(self,root):ifnotroot:return[]returnself.dfs(root.left)+[root.val]+self.dfs(root.right)#通过二叉数组构建平衡二叉树defbuild(self,nums:List[int])->TreeNode:ifnotnums:returnNonemid=len(nums)//2node=TreeNode(nums[mid])left=nums[:mid]right=nums[mid+1:]node.left=self.build(left)node.right=self.build（右）返回节点代码地址GitHub链接
