【什么是平衡二叉树】【如何构建平衡二叉树】【（字节面试题）判断是否为平衡二叉树】

欢迎观看我的博客，如有问题交流，欢迎评论区留言，一定尽快回复！（大家可以去看我的专栏，是所有文章的目录）
文章字体风格：
红色文字表示：重难点
蓝色文字表示：思路以及想法
　
如果大家觉得有帮助的话，感谢大家帮忙点赞！收藏！转发！

1. 什么是平衡二叉树

平衡二叉树满足以下条件：

1. 左右子树的高度差 不 大于等于2
2. 左子树小于根节点，右子树大于根节点

2. 如何构建平衡二叉树

2 种「旋转」方式：

1. 左旋：
   旧根节点为新根节点的左子树
   新根节点的左子树（如果存在）为旧根节点的右子树

2. 右旋：
   旧根节点为新根节点的右子树
   新根节点的右子树（如果存在）为旧根节点的左子树

4 种「旋转」纠正类型：

1. LL 型：插入左孩子的左子树，右旋
2. RR 型：插入右孩子的右子树，左旋
3. LR 型：插入左孩子的右子树，先左旋，再右旋
4. RL 型：插入右孩子的左子树，先右旋，再左旋

修改后的

操作：

1. 把3改为2的右子树
2. 把1改为2的左子树
3. 先把1改为2的左子树，然后3改为2的右子树
4. 先把3改为2的右子树，再把1改为2的左子树

例题 案例4-1.3 平衡二叉树的根

#include 
#include 
#define ElemType int
typedef struct BiTNode {
    ElemType Data;
    struct BiTNode *Left;
    struct BiTNode *Right;
}*AVLTree;
AVLTree SingleLeftRotation(AVLTree T) {//左单旋
    AVLTree B=T->Left;
    T->Left=B->Right;
    B->Right=T;
    return B;
}
AVLTree SingleRightRotation(AVLTree T) {//右单旋
    AVLTree B=T->Right;
    T->Right=B->Left;
    B->Left=T;
    return B;
}
AVLTree DoubleLeftRightRotation(AVLTree T) {//左右双旋
    T->Left=SingleRightRotation(T->Left);
    return SingleLeftRotation(T);
}
AVLTree DoubleRightLeftRotation(AVLTree T) {//右左双旋
    T->Right=SingleLeftRotation(T->Right);
    return SingleRightRotation(T);
}
 
AVLTree Insert(AVLTree T,ElemType X) {
    if(!T) {
        T=(AVLTree)malloc(sizeof(AVLTree));//每次新插入结点需申请空间
        T->Data=X;
        T->Left=NULL;
        T->Right=NULL;
    } else {
        if(X>T->Data) {//往右子树找位置
            T->Right=Insert(T->Right,X);
            if(GetHeight(T->Right)-GetHeight(T->Left)==2) {
                if(X<T->Right->Data) {
                    T=DoubleRightLeftRotation(T);
                } else T=SingleRightRotation(T);
            }
        } else if(X<T->Data) {//往左子树找位置
            T->Left=Insert(T->Left,X);
            if(GetHeight(T->Left)-GetHeight(T->Right)==2) {
                if(X>T->Left->Data) {
                    T=DoubleLeftRightRotation(T);
                } else T=SingleLeftRotation(T);
            }
        }
    }
    return T;
 
}
int GetHeight(AVLTree T) {//求树高
    if(!T)
        return 0;
    int hl=GetHeight(T->Left);
    int hr=GetHeight(T->Right);
    return (hl>hr?hl:hr)+1;
}
int main() {
    int n,x,i;
    scanf("%d",&n);
    AVLTree T=NULL;//初始化为NULL;
    for(i=0; i<n; i++) {
        scanf("%d",&x);
        T=Insert(T,x);
    }
    printf("%d",T->Data);
    return 0;
}
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

构建思路

1. 写一个获取树高度的函数

int GetHeight(AVLTree T) {//求树高
    if(!T)
        return 0;
    int hl=GetHeight(T->Left);
    int hr=GetHeight(T->Right);
    return (hl>hr?hl:hr)+1;
1
2
3
4
5
6

2. 每次插入都是从头结点开始遍历，
3. 比较高度的时候，比较的是 左右孩子节点的高度

3. 判断是不是平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);
        if(Math.abs(leftDepth - rightDepth) > 1) return false;
        return isBalanced(root.left) && isBalanced(root.right);
    }

    public int getDepth(TreeNode node){
        if(node == null) return 0;
        int leftdepth = getDepth(node.left);
        int rightdepth = getDepth(node.right);
        return Math.max(leftdepth, rightdepth) + 1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14