题目描述
给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。
如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
代码实现
class Solution {
public TreeNode
balanceBST(TreeNode root
) {
List
<Integer> nodes
= new ArrayList<>();
getNodes(root
,nodes
);
return inBST(nodes
,0,nodes
.size()-1);
}
public void getNodes(TreeNode root
, List
<Integer> nodes
){
if(root
!= null
){
getNodes(root
.left
, nodes
);
nodes
.add(root
.val
);
getNodes(root
.right
, nodes
);
}
}
public TreeNode
inBST(List
<Integer> nodes
,int left
, int right
){
if(left
>right
) return null
;
int mid
= left
+ (right
- left
)/2;
TreeNode root
= new TreeNode(nodes
.get(mid
));
root
.left
= inBST(nodes
,left
, mid
- 1);
root
.right
= inBST(nodes
,mid
+1,right
);
return root
;
}
}
问题出现在 最后选二叉树的根结点和108题有点不一样 但应该都对
