题目大意：
将二叉搜索树变平衡
给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。
如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 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之间。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1382
解题思路分析：
这道题难度不大，我们需要两个步骤，第一，先将原始的二叉搜索树还原成数组，该数组是升序排序的。然后我们再使用二分法重组二叉树即可。
解题时，将二叉查找树变成排序数组的方式是使用中序遍历（递归左子节点，打印当前节点节点，递归右子节点顺序）。还原二叉查找树时，我们同样需要使用到递归，递归方法中首先取出数组中间值为二叉树根节点，然后以当前下标将数组一分为二，左半边递归到子问题，它的返回值为当前节点的左子节点，右半部分同样递归到子问题，它的返回值为当前节点的右子节点。
实现代码：
// 存储二叉树所有节点
List<Integer> list=new ArrayList<>();
public TreeNode balanceBST(TreeNode root) {
// 中序遍历二叉树，取得树中所有节点
inOrder(root);
// 使用二分递归，新建二叉搜索树
return help(0,list.size()-1);
}
void inOrder(TreeNode root){
if(root.left!=null) inOrder(root.left);
list.add(root.val);
if(root.right!=null) inOrder(root.right);
}
// l：二分范围左边界
// r：二分范围右边界
TreeNode help(int l, int r){
// 区间范围不合理，返回空
if(l>r) return null;
// 取得中间点
int mid=(l+r)/2;
// 中间点为当前节点
TreeNode node = new TreeNode(list.get(mid));
// 利用当前节点，将区间分为左右两部分
// 将左半部分递归至子问题，其返回值为当前节点左子节点
node.left=help(l,mid-1);
// 将右半部分递归至子问题，其返回值为当前节点右子节点
node.right=help(mid+1,r);
// 返回当前节点
return node;
} 本题解法执行时间为2ms。
Runtime: 2 ms, faster than 99.76% of Java online submissions for Balance a Binary Search Tree.
Memory Usage: 43.5 MB, less than 100.00% of Java online submissions for Balance a Binary Search Tree.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1382-balance-a-binary-search-tree/