05 August 2008
给一棵BST，返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。
如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，称这棵二叉搜索树是 平衡的 。
如果有多种构造方法，返回任意一种。
事先熟悉第98和108题
这题利用中序遍历把二叉树转变为有序数组，然后在根据有序数组构造平衡二叉搜索树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
ArrayList <Integer> result = new ArrayList<>();
// 有序树转成有序数组
private void travesal(TreeNode cur) {
if (cur == null) return;
travesal(cur.left);
result.add(cur.val);
travesal(cur.right);
}
// 有序数组转成平衡二叉树
private TreeNode getTree(ArrayList <Integer> nums, int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(nums.get(mid));
root.left = getTree(nums, left, mid - 1);
root.right = getTree(nums, mid + 1, right);
return root;
}
public TreeNode balanceBST(TreeNode root) {
travesal(root);
return getTree(result, 0, result.size() - 1);
}
}