例题：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
经典法
通过左旋右旋构建平衡二叉树，不要求序列是有序的
当检测到被破坏的结点，即该结点｜HL - HR｜> 1 时。用LL，RR，LR，RL四种方式对二叉树结点进行平衡，可以理解为对二叉树的插入操作增加了判断，并根据判断进行平衡操作。
HL为左子树高度，HR为右子树高度。LL为左单旋，RR为右单旋，LR为左右双旋，RL为右左双旋
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
TreeNode root = null;
for(int i = 0; i < nums.length; i++){
root = insert(root,nums[i]);
}
return root;
}
public TreeNode insert(TreeNode root,int val){
if(root == null){
root = new TreeNode(val,null,null);
return root;
}
if(val < root.val){
root.left = insert(root.left,val);
if(getHeight(root.left) - getHeight(root.right) == 2){
if(val < root.left.val){
root = singleLeftRotation(root);
}else{
root = doubleLeftRightRotation(root);
}
}
}else if(val > root.val){
root.right = insert(root.right,val);
if(getHeight(root.left) - getHeight(root.right) == -2){
if(val > root.right.val){
root = singleRightRotation(root);
}else{
root = doubleRightLeftRotation(root);
}
}
}
return root;
}
public int getHeight(TreeNode root){
if(root == null){
return 0;
}
int HL = getHeight(root.left);
int HR = getHeight(root.right);
return Math.max(HL,HR) + 1;
}
public TreeNode singleLeftRotation(TreeNode a){
TreeNode b = a.left;
a.left = b.right;
b.right = a;
return b;
}
public TreeNode singleRightRotation(TreeNode a){
TreeNode b = a.right;
a.right = b.left;
b.left = a;
return b;
}
public TreeNode doubleLeftRightRotation(TreeNode a){
a.left = singleRightRotation(a.left);
return singleLeftRotation(a);
}
public TreeNode doubleRightLeftRotation(TreeNode a){
a.right = singleLeftRotation(a.right);
return singleRightRotation(a);
}
}
|
将升序序列转换为平衡二叉树
取序列的中间节点作为根结点，要求序列是递增的
由于序列是递增的，则该序列可以看成搜索树的中序遍历。我们可以选择序列的中间数字作为搜索树的根节点，其左边作为左子树，右边作为右子树。这样分给左右子树的数字个数相同或只相差 1，可以使树保持平衡。由于每个结点都要满足这个条件，则我们可以进行递归处理，使左子树序列的中间节点作为左子树的根结点，右子树序列的中间节点作为右子树的根结点，以此类推
如果数组长度是奇数，则根节点就为中间节点；如果数组长度是偶数，则可以选择中间位置左边的数字作为根节点或者选择中间位置右边的数字作为根节点，选择不同的数字作为根节点创建的平衡二叉搜索树也是不同的。
例如：
1
2
3
4
5
6
7
8
9
10
11
12
13
| 递增序列[1,2,3,4,5,6,7,8]
我们先取中间数字(4.5)的左边 4作为树的根结点，此时左子树为[1,2,3]，右子树为[5,6,7,8]
再取左子树的中间数字2作为左子树的根结点，右子树的中间数字的左边6作为右子树的根结点
……
4
2 6
1 3 5 7
8
|
实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return createAVL(nums,0,nums.length - 1);
}
public TreeNode createAVL(int[] nums,int left,int right){
if(left > right){
return null;
}
int mid = (left + right)/2;
TreeNode root = new TreeNode(nums[mid]);
root.left = createAVL(nums,left,mid - 1);
root.right = createAVL(nums,mid + 1,right);
return root;
}
}
|
微信
支付宝
