平衡二叉树、AVL树

目录

一，概念辨析

1，平衡无序二叉树

2，平衡排序二叉树（Self-balancing binary search tree）

3，平衡二叉树

4，AVL树

二，查询

三，插入节点

1，插入一个新节点，变成二叉排序树

2，调整深度使得它变成平衡二叉树

（1）不平衡点的分布

（2）最近不平衡点

（3）调整深度

3，完整插入代码（版本一）

四，删除节点

1，插入代码重构

2，完整插入代码（版本二）

3，插入调整的另外一个思路——覆盖旋转

4，完整插入代码（版本三）

5，删除节点

五，OJ实战

1，平衡无序二叉树

力扣 110. 平衡二叉树

2，平衡排序二叉树

力扣 108. 将有序数组转换为二叉搜索树

力扣 109. 有序链表转换二叉搜索树

---

一，概念辨析

1，平衡无序二叉树

其实并没有“平衡无序二叉树”这个词，但是“平衡二叉树”这个词的概念一直有两个流派，为了区分，我发明了这个词。

如果一个二叉树满足任意节点的俩子树的高度差都小于等于1，那么它就是平衡无序二叉树。

完全二叉树就是一种平衡无序二叉树。

PS：如若任意节点的俩子树的高度差都为0，那它就只能是满二叉树了。

2，平衡排序二叉树（Self-balancing binary search tree）

如果一个二叉树，既是平衡无序二叉树，又是二叉搜索树（二叉排序树），则称之为平衡排序二叉树。

3，平衡二叉树

关于平衡二叉树，有很多人认为指的是平衡无序二叉树，也有很多人认为是平衡排序二叉树。

从字面意思来看，是平衡无序二叉树，但是从实际应用场景来看，一般指的都是平衡排序二叉树。

我支持平衡二叉树就是平衡排序二叉树的简称这一观点，毕竟都是从英文翻译来的，名称不准确。

4，AVL树

AVL树，取自人名，是最早发明的一种平衡排序二叉树。

也有很多人直接用平衡二叉树指代AVL树，虽然不严谨，但是能理解这个意思就行。

下文全部都是关于AVL树的内容。

二，查询

平衡二叉树作为一棵二叉搜索树，查询的过程和普通二叉搜索树二叉搜索树（BST）_csuzhucong的博客-CSDN博客_二叉查找树完全相同。

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};
 
TreeNode* find(TreeNode* root, int val)
{
    if(!root)return NULL;
    if(root->val==val)return root;
    if(root->val>val)return find(root->left,val);
    return find(root->right,val);
}

//find first node.val > val
Treenode* findBig(Treenode* root, int val)
{
	if (!root)return NULL;
	if (root->val <= val)return findBig(root->right, val);
	auto ans = findBig(root->left, val);
	return ans? ans:root;
}
//find last node.val < val
Treenode* findSmall(Treenode* root, int val)
{
	if (!root)return NULL;
	if (root->val >= val)return findSmall(root->left, val);
	auto ans = findSmall(root->right, val);
	return ans ? ans : root;
}

三，插入节点

插入节点分为两步，先插入一个新节点，变成二叉排序树，如果它不是平衡二叉树，那么就进行第二步，调整深度使得它变成平衡二叉树。

神奇的是，这两步是解耦的，第一步采取什么样的方案不影响第二步的策略，只要第一步的插入操作是正规插入。

这里的正规插入指的是，在某个节点A下，把new节点插入到A和A的某个子树（子树可能为空）中间，除此之外不对原树进行任何修改。

1，插入一个新节点，变成二叉排序树

这一步可以有很多方案，只要满足上面说的正规插入即可。

例如，可以和二叉排序树的插入节点的方法一样，找到某个位置插入new节点之后，new节点是叶子节点。

如果采取这种方案的话，插入代码就和二叉搜索树里面的完全一样。

void InsertNode(TreeNode* &root, TreeNode* node)
{
    if(!root)root=node;
    else if(root->val>node->val)InsertNode(root->left,node);
    else InsertNode(root->right,node);
}

2，调整深度使得它变成平衡二叉树

（1）不平衡点的分布

插入new节点之后，如果对于某个节点A，以A为根的二叉树不是平衡二叉树，我们称之为不平衡点。

从根节点到new节点的最短路径中，一定包含了所有的不平衡点。

在这条路径上，不平衡点的分布又有什么规律呢？

举个栗子：

可以说有规律，和节点两边的高度差有关，如果高度差是1，然后刚好在高度更高的那边插入了叶子节点并且使得高度加1，那么就会产生一个不平衡点。

PS：有可能有若干个不平衡点，但是这些点中不包含root节点。

PPS：无论整棵树的高度有没有加1，都有可能有若干个不平衡点，但是这些点中不包含root节点。

（2）最近不平衡点

在所有不平衡点中，找到离new节点最近的那个，我们称之为最近不平衡点N。

只要采取正规调整法，使得以N为根的树变成平衡二叉树，其他的不平衡点都会自动消失，整颗树都会变成平衡二叉树。

这里的正规调整指的是，让new节点所在的子树的深度减1，这样以N为根的树就变成平衡二叉树了，此时，以N为根的树的深度也减1了，而所有不平衡点又都是N的祖先，于是所有的不平衡点都消失了。

寻找最近不平衡点的代码：

//ans是出参，返回值是深度
int GetNearestNoBalanceNode(TreeNode* root, TreeNode* &ans)
{
    if(!root)return 0;
    int d1=GetNearestNoBalanceNode(root->left,ans);
    int d2=GetNearestNoBalanceNode(root->right,ans);
    if(d1<0 || d2<0)return -1;
    if(d1-d2>1 || d2-d1>1){
        ans=root;
        return -1;
    }
    ans = NULL;
    return ((d1<d2)?d2:d1)+1;
}

最终结果为空指针就代表没有不平衡点

（3）调整深度

new节点一定不是N节点（最近不平衡点），也不是N节点的孩子，即两者的深度差至少是二。

N节点的孩子的孩子一共有4个，LL，RR，LR，RL，这四个里面有一个是new节点的祖先（包括就是new节点的情况）

首先确定，到底哪一个是new节点的祖先：

void CC(TreeNode* root, TreeNode* node, TreeNode* &c1, TreeNode* &c2)
{
    if(root->val>node->val)c1=root->left;
    else c1=root->right;
    if(c1->val>node->val)c2=c1->left;
    else c2=c1->right;
}

root是最近不平衡点，c1是root的孩子，c2是c1的孩子，c2就是new节点的祖先。

因为new节点的存在性，所以这里不需要指针判空。

后来发现CC函数有BUG，从空树开始插入顺序是{ 26, 20, 34, 6, 23, 27, 4, 15, 7, 21, 11, 28, 2, 1, 22, 3, 16, 33, 5, 31, 12, 13, 25, 14, 19, 35, 32, 29, 18, 24, 8, 9, 17, 10, 30 }时CC内访问空指针了。

然后通过旋转，让c1和c2的位置互换：

void RotateLL(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
    root->left=c2,c1->left=c1->right,c1->right=root->right,root->right=c1;
    int val=root->val;
    root->val=c1->val,c1->val=val;
}
void RotateRR(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
    root->right=c2,c1->right=c1->left,c1->left=root->left,root->left=c1;
    int val=root->val;
    root->val=c1->val,c1->val=val;
}
void RotateLR(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
    root->left=c2,c1->right=c2->left,c2->left=c1;
    RotateLL(root,c2,c1);
}
void RotateRL(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
    root->right=c2,c1->left=c2->right,c2->right=c1;
    RotateRR(root,c2,c1);
}
void Rotate(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
    if(root->left==c1){
        if(c1->left==c2)RotateLL(root,c1,c2);
        else RotateLR(root,c1,c2);
    } else{
        if(c1->left==c2)RotateRL(root,c1,c2);
        else RotateRR(root,c1,c2);
    }
}

最后，综合起来就得到了完整了深度调整方案：

void Adjust(TreeNode* root, TreeNode* node)
{
    TreeNode*p,*c1,*c2;
    GetNearestNoBalanceNode(root,p);
    if(p==NULL)return;
    CC(p,node,c1,c2);
    Rotate(p,c1,c2);
}

下文的力扣 108、109这2个题目中直接用我这个插入接口做的，所以就不需要再额外做测试了。

3，完整插入代码（版本一）

void InsertNode(TreeNode* &root, TreeNode* node)
{
    if(!root)root=node;
    else if(root->val>node->val)InsertNode(root->left,node);
    else InsertNode(root->right,node);
}

//ans是出参，返回值是深度
int GetNearestNoBalanceNode(TreeNode* root, TreeNode* &ans)
{
    if(!root)return 0;
    int d1=GetNearestNoBalanceNode(root->left,ans);
    int d2=GetNearestNoBalanceNode(root->right,ans);
    if(d1<0 || d2<0)return -1;
    if(d1-d2>1 || d2-d1>1){
        ans=root;
        return -1;
    }
    ans = NULL;
    return ((d1<d2)?d2:d1)+1;
}

void CC(TreeNode* root, TreeNode* node, TreeNode* &c1, TreeNode* &c2)
{
    if(root->val>node->val)c1=root->left;
    else c1=root->right;
    if(c1->val>node->val)c2=c1->left;
    else c2=c1->right;
}

void RotateLL(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
    root->left=c2,c1->left=c1->right,c1->right=root->right,root->right=c1;
    int val=root->val;
    root->val=c1->val,c1->val=val;
}
void RotateRR(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
    root->right=c2,c1->right=c1->left,c1->left=root->left,root->left=c1;
    int val=root->val;
    root->val=c1->val,c1->val=val;
}
void RotateLR(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
    root->left=c2,c1->right=c2->left,c2->left=c1;
    RotateLL(root,c2,c1);
}
void RotateRL(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
    root->right=c2,c1->left=c2->right,c2->right=c1;
    RotateRR(root,c2,c1);
}
void Rotate(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
    if(root->left==c1){
        if(c1->left==c2)RotateLL(root,c1,c2);
        else RotateLR(root,c1,c2);
    } else{
        if(c1->left==c2)RotateRL(root,c1,c2);
        else RotateRR(root,c1,c2);
    }
}

void Adjust(TreeNode* root, TreeNode* node)
{
    TreeNode*p,*c1,*c2;
    GetNearestNoBalanceNode(root,p);
    if(p==NULL)return;
    CC(p,node,c1,c2);
    Rotate(p,c1,c2);
}

void InsertAndAdjust(TreeNode* &root, int val)
{
    TreeNode* p = find(root,val);
    if(p)return;
    p= new TreeNode();
    p->val=val;
    p->left=NULL, p->right=NULL;
    InsertNode(root,p);
    Adjust(root,p);
}

四，删除节点

删除节点的思路，比插入节点的思路更复杂。

1，插入代码重构

在写插入节点的代码时，我就已经注意到，CC函数和Rotate函数的逻辑基本是重复的。

CC函数是new节点和最近不平衡点的位置关系，结果是LL，LR，RL，RR四种，Rotate函数是根据CC函数的结果来确认调用哪个函数。

其中CC函数的实现，有2种思路，一种是根据new节点的val值来计算，一种是根据两边的深度来计算，虽然结果是一样的，但是其实深度才是本质。

我把LL和LR两种情况的图示画出来了：

ABC是节点，1234是四颗树，其中，A就是最近不平衡点，3或者4就是插入new节点的位置，插入之后3或4的长度减1的长度等于二。
经过调整后，1的长度加一，3和4的长度减一，2的长度不变，于是就变成了平衡二叉树。
其他的，比如LL中，1和2都变成了A的子树，那么A还是平衡二叉树吗？是的，这个是可以推导出来的，其他的也是。

再次重申，3和4都有可能是空树，甚至都是空树，new节点可能就是C，这不影响我们的计算，甚至自然语言的描述都是一致的。

至此，我们就得到了关于插入节点之后如何调整的更有力的表述：

先找到不平衡点A，计算两颗子树的深度，深度差一定刚好是2，通过简单的调整，两颗子树的深度分别加1和减1，调整之后两边深度相等。

基于此，我们可以把插入的代码进行微重构：

首先，删掉CC函数，并修改Rotate函数：

int maxDepth(TreeNode* root) {
    if (!root)return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
void Rotate(TreeNode* root)
{
    if (maxDepth(root->left) > maxDepth(root->right) + 1) {
        if (maxDepth(root->left->left) > maxDepth(root->left->right))RotateLL(root, root->left, root->left->left);
        else RotateLR(root, root->left, root->left->right);
    } else if (maxDepth(root->right) > maxDepth(root->left) + 1) {
        if (maxDepth(root->right->right) > maxDepth(root->right->left))RotateRR(root, root->right, root->right->right);
        else RotateRL(root, root->right, root->right->left);
    }
}

void Adjust(TreeNode* root, TreeNode* node)
{
    TreeNode* p, * c1, * c2;
    GetNearestNoBalanceNode(root, p);
    if (p == NULL)return;
    Rotate(p);
}

其次，我们发现各个旋转函数其实并不需要传参，可进一步重构。

2，完整插入代码（版本二）

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

void InsertNode(TreeNode*& root, TreeNode* node)
{
    if (!root)root = node;
    else if (root->val > node->val)InsertNode(root->left, node);
    else InsertNode(root->right, node);
}

//ans是出参，返回值是深度
int GetNearestNoBalanceNode(TreeNode* root, TreeNode*& ans)
{
    if (!root)return 0;
    int d1 = GetNearestNoBalanceNode(root->left, ans);
    int d2 = GetNearestNoBalanceNode(root->right, ans);
    if (d1 < 0 || d2 < 0)return -1;
    if (d1 - d2 > 1 || d2 - d1 > 1) {
        ans = root;
        return -1;
    }
    ans = NULL;
    return ((d1 < d2) ? d2 : d1) + 1;
}

int maxDepth(TreeNode* root) {
    if (!root)return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

void RotateLL(TreeNode* root)
{
    TreeNode* c1 = root->left, * c2 = c1->left;
    root->left = c2, c1->left = c1->right, c1->right = root->right, root->right = c1;
    int val = root->val;
    root->val = c1->val, c1->val = val;
}
void RotateRR(TreeNode* root)
{
    TreeNode* c1 = root->right, * c2 = c1->right;
    root->right = c2, c1->right = c1->left, c1->left = root->left, root->left = c1;
    int val = root->val;
    root->val = c1->val, c1->val = val;
}
void RotateLR(TreeNode* root)
{
    TreeNode* c1 = root->left, * c2 = c1->right;
    root->left = c2, c1->right = c2->left, c2->left = c1;
    RotateLL(root);
}
void RotateRL(TreeNode* root)
{
    TreeNode* c1 = root->right, * c2 = c1->left;
    root->right = c2, c1->left = c2->right, c2->right = c1;
    RotateRR(root);
}

void Rotate(TreeNode* root)
{
    if (maxDepth(root->left) > maxDepth(root->right) + 1) {
        if (maxDepth(root->left->left) > maxDepth(root->left->right))RotateLL(root);
        else RotateLR(root);
    } else if (maxDepth(root->right) > maxDepth(root->left) + 1) {
        if (maxDepth(root->right->right) > maxDepth(root->right->left))RotateRR(root);
        else RotateRL(root);
    }
}

void Adjust(TreeNode* root, TreeNode* node)
{
    TreeNode* p;
    GetNearestNoBalanceNode(root, p);
    if (p == NULL)return;
    Rotate(p);
}

void InsertAndAdjust(TreeNode*& root, int val)
{
    TreeNode* p = find(root,val);
    if(p)return;
    p= new TreeNode();
    p->val = val;
    p->left=NULL, p->right=NULL;
    InsertNode(root, p);
    Adjust(root, p);
}

int main()
{
    TreeNode* root = NULL;
    InsertAndAdjust(root, -10);
    InsertAndAdjust(root, -3);
    InsertAndAdjust(root, 0);
    InsertAndAdjust(root, 5);
    InsertAndAdjust(root, 9);
    return 0;
}

当然，这个版本也还有很多可以改进的地方，比如maxDepth函数调用多次，影响效率，这个很容易优化掉，不过并不是我们的主逻辑，略过。

这里得到的Rotate函数有个巨大的价值就在于，它可以直接通用于插入场景和删除场景。

3，插入调整的另外一个思路——覆盖旋转

前面的思路是，先找到最近不平衡点，对这个节点调用Rotate函数即可平衡，而且此时整棵树都会变成平衡二叉树，不再有不平衡点。

插入和删除最大的区别在于，删除一个节点并消除最近不平衡点之后，可能还有很多很多不平衡点等待消除。

当然，共同点就是，所有的不平衡点依然是删除节点的祖先。

如果把插入节点或者删除节点的所有祖先全部调用一次Rotate函数，那么整颗树就会变成平衡二叉树，我们也会得到更加通用的代码。

要实现这个覆盖，有两种方式，一种是从插入节点或者删除节点向上一直到root依次调用，一种是按照后续遍历把所有节点都依次调用一遍。

这里我们来实现后者。

删除GetNearestNoBalanceNode函数，并修改Adjust函数：

void Adjust(TreeNode* root)
{
    if (!root)return;
    Adjust(root->left);
    Adjust(root->right);
    Rotate(root);
}

进一步的，Adjust函数和Rotate函数可以融合到一起，减少maxDepth函数的调用次数。

int Adjust(TreeNode* root)
{
    if (!root)return 0;
    int dl = Adjust(root->left);
    int dr = Adjust(root->right);
    if(dl>dr+1){
        if (maxDepth(root->left->left) > maxDepth(root->left->right))RotateLL(root);
        else RotateLR(root);
        return dl;
    } else if(dr>dl+1){
        if (maxDepth(root->right->right) > maxDepth(root->right->left))RotateRR(root);
        else RotateRL(root);
        return dr;
    }
    return max(dl,dr)+1;
}

能不能在Adjust函数递归的过程中，记录更多的信息，从而直接抛弃maxDepth函数呢？

这块我没有深入研究，因为当前版本的性能虽然不高但是足够通过下面的力扣 108题了，也就可以校验逻辑正确性了。

4，完整插入代码（版本三）

#include <iostream>
#include<algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

void InsertNode(TreeNode*& root, TreeNode* node)
{
    if (!root)root = node;
    else if (root->val > node->val)InsertNode(root->left, node);
    else InsertNode(root->right, node);
}

int maxDepth(TreeNode* root) {
    if (!root)return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

void RotateLL(TreeNode* root)
{
    TreeNode* c1 = root->left, * c2 = c1->left;
    root->left = c2, c1->left = c1->right, c1->right = root->right, root->right = c1;
    int val = root->val;
    root->val = c1->val, c1->val = val;
}
void RotateRR(TreeNode* root)
{
    TreeNode* c1 = root->right, * c2 = c1->right;
    root->right = c2, c1->right = c1->left, c1->left = root->left, root->left = c1;
    int val = root->val;
    root->val = c1->val, c1->val = val;
}
void RotateLR(TreeNode* root)
{
    TreeNode* c1 = root->left, * c2 = c1->right;
    root->left = c2, c1->right = c2->left, c2->left = c1;
    RotateLL(root);
}
void RotateRL(TreeNode* root)
{
    TreeNode* c1 = root->right, * c2 = c1->left;
    root->right = c2, c1->left = c2->right, c2->right = c1;
    RotateRR(root);
}

int Adjust(TreeNode* root)
{
    if (!root)return 0;
    int dl = Adjust(root->left);
    int dr = Adjust(root->right);
    if(dl>dr+1){
        if (maxDepth(root->left->left) > maxDepth(root->left->right))RotateLL(root);
        else RotateLR(root);
        return dl;
    } else if(dr>dl+1){
        if (maxDepth(root->right->right) > maxDepth(root->right->left))RotateRR(root);
        else RotateRL(root);
        return dr;
    }
    return max(dl,dr)+1;
}

void InsertAndAdjust(TreeNode*& root, int val)
{
    TreeNode* p = find(root,val);
    if(p)return;
    p= new TreeNode();
    p->val = val;
    p->left=NULL, p->right=NULL;
    InsertNode(root, p);
    Adjust(root);
}

int main()
{
    TreeNode* root = NULL;
    InsertAndAdjust(root, -10);
    InsertAndAdjust(root, -3);
    InsertAndAdjust(root, 0);
    InsertAndAdjust(root, 5);
    InsertAndAdjust(root, 9);
    return 0;
}

5，删除节点

基于以上的重构工作，删除节点就变得十分简单了。

平衡二叉树删除节点分两步：

（1）删除一个节点，得到二叉搜索树，代码和二叉搜索树删除节点完全相同

（2）调整深度，得到平衡二叉树，代码和平衡二叉树插入节点（版本三）完全相同

注意：虽然插入和删除节点的调整深度的过程是一样的，都是调用Adjust函数，但是两种场景下的树深度变化规律却是不完全相同。

相同点是，都是按照后序遍历依次调整所有节点，都只有不平衡点才有实际调整操作，平衡点啥都不做，不平衡点都是两边子树的深度差为2

不同点是，插入节点后调用Adjust函数，两颗子树的深度分别加1和减1，调整之后两边深度相等，树的深度减1，

删除节点后调用Adjust函数，两颗子树的深度分别加1 和 “减1或不变”，调整之后两边深度相等或相差1，树的深度减1或不变。

PS：调用Adjust函数对子树的影响，取决于代码细节，如果maxDepth(root->left->left) > maxDepth(root->left->right)的条件改成>=，那上面的表述又略有差异。

删除节点完整代码：

TreeNode* GetMin(TreeNode* root)
{
    if (!root)return root;
    if (root->left)return GetMin(root->left);
    return root;
}

TreeNode* GetParent(TreeNode* root, TreeNode* node)
{
    if (!root || root == node || root->left == node || root->right == node)return root;
    if (root->val > node->val)return GetParent(root->left, node);
    return GetParent(root->right, node);
}

void DeleteNode(TreeNode*& node)
{
    if (node->left == NULL) {
        node = node->right;
        return;
    }
    if (node->right == NULL) {
        node = node->left;
        return;
    }
    TreeNode* thenext = GetMin(node->right);
    if (thenext == node->right) {
        thenext->left = node->left, node = thenext;
        return;
    }
    node->val = thenext->val;
    TreeNode* p = GetParent(node, thenext);
    p->left = thenext->right;
}

int maxDepth(TreeNode* root) {
    if (!root)return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

void RotateLL(TreeNode* root)
{
    TreeNode* c1 = root->left, * c2 = c1->left;
    root->left = c2, c1->left = c1->right, c1->right = root->right, root->right = c1;
    int val = root->val;
    root->val = c1->val, c1->val = val;
}
void RotateRR(TreeNode* root)
{
    TreeNode* c1 = root->right, * c2 = c1->right;
    root->right = c2, c1->right = c1->left, c1->left = root->left, root->left = c1;
    int val = root->val;
    root->val = c1->val, c1->val = val;
}
void RotateLR(TreeNode* root)
{
    TreeNode* c1 = root->left, * c2 = c1->right;
    root->left = c2, c1->right = c2->left, c2->left = c1;
    RotateLL(root);
}
void RotateRL(TreeNode* root)
{
    TreeNode* c1 = root->right, * c2 = c1->left;
    root->right = c2, c1->left = c2->right, c2->right = c1;
    RotateRR(root);
}

int Adjust(TreeNode* root)
{
    if (!root)return 0;
    int dl = Adjust(root->left);
    int dr = Adjust(root->right);
    if(dl>dr+1){
        if (maxDepth(root->left->left) > maxDepth(root->left->right))RotateLL(root);
        else RotateLR(root);
        return dl;
    } else if(dr>dl+1){
        if (maxDepth(root->right->right) > maxDepth(root->right->left))RotateRR(root);
        else RotateRL(root);
        return dr;
    }
    return max(dl,dr)+1;
}

测试代码：

int main()
{
    TreeNode* root=NULL;
    InsertAndAdjust(root, 10);
    InsertAndAdjust(root, 3);
    InsertAndAdjust(root, 0);
    InsertAndAdjust(root, 5);
    InsertAndAdjust(root, 9);
    InsertAndAdjust(root, 2);
    InsertAndAdjust(root, 4);
    InsertAndAdjust(root, 7);
    InsertAndAdjust(root, 1);
    DeleteNode(root->right);
    Adjust(root);
    return 0;
}

五，OJ实战

1，平衡无序二叉树

力扣 110. 平衡二叉树

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

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：

输入：root = []
输出：true
 

提示：

树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104

代码：

class Solution {
public:
	int maxDepth(TreeNode* root) {
		if (!root)return 0;
		int d1 = maxDepth(root->left), d2 = maxDepth(root->right);
		if (d1<0 || d2<0 || d1 - d2 > 1 || d2 - d1 > 1)return -1;
		return max(d1,d2) + 1;
	}
	bool isBalanced(TreeNode* root) {
		return maxDepth(root) >= 0;
	}
};

2，平衡排序二叉树

力扣 108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
 

提示：

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 按 严格递增 顺序排列

代码：

void InsertNode(TreeNode* &root, TreeNode* node)
{
    if(!root)root=node;
    else if(root->val>node->val)InsertNode(root->left,node);
    else InsertNode(root->right,node);
}

//ans是出参，返回值是深度
int GetNearestNoBalanceNode(TreeNode* root, TreeNode* &ans)
{
    if(!root)return 0;
    int d1=GetNearestNoBalanceNode(root->left,ans);
    int d2=GetNearestNoBalanceNode(root->right,ans);
    if(d1<0 || d2<0)return -1;
    if(d1-d2>1 || d2-d1>1){
        ans=root;
        return -1;
    }
    ans = NULL;
    return ((d1<d2)?d2:d1)+1;
}

void CC(TreeNode* root, TreeNode* node, TreeNode* &c1, TreeNode* &c2)
{
    if(root->val>node->val)c1=root->left;
    else c1=root->right;
    if(c1->val>node->val)c2=c1->left;
    else c2=c1->right;
}

void RotateLL(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
    root->left=c2,c1->left=c1->right,c1->right=root->right,root->right=c1;
    int val=root->val;
    root->val=c1->val,c1->val=val;
}
void RotateRR(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
    root->right=c2,c1->right=c1->left,c1->left=root->left,root->left=c1;
    int val=root->val;
    root->val=c1->val,c1->val=val;
}
void RotateLR(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
    root->left=c2,c1->right=c2->left,c2->left=c1;
    RotateLL(root,c2,c1);
}
void RotateRL(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
    root->right=c2,c1->left=c2->right,c2->right=c1;
    RotateRR(root,c2,c1);
}
void Rotate(TreeNode* root, TreeNode* c1, TreeNode* c2)
{
    if(root->left==c1){
        if(c1->left==c2)RotateLL(root,c1,c2);
        else RotateLR(root,c1,c2);
    } else{
        if(c1->left==c2)RotateRL(root,c1,c2);
        else RotateRR(root,c1,c2);
    }
}

void Adjust(TreeNode* root, TreeNode* node)
{
    TreeNode*p,*c1,*c2;
    GetNearestNoBalanceNode(root,p);
    if(p==NULL)return;
    CC(p,node,c1,c2);
    Rotate(p,c1,c2);
}

void InsertAndAdjust(TreeNode* &root, int val)
{
    TreeNode* p= new TreeNode();
    p->val=val;
    p->left=NULL, p->right=NULL;
    InsertNode(root,p);
    Adjust(root,p);
}

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode*root=NULL;
        for(int i=0;i<nums.size();i++)InsertAndAdjust(root, nums[i]);
        return root;
    }
};

力扣 109. 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

//省略若干函数，同力扣108

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        TreeNode*root=NULL;
        while(head){
            InsertAndAdjust(root,head->val);
            head=head->next;
        }
        return root;
    }
};