讨论/题目交流/🏆 第 180 场力扣周赛/
🏆 第 180 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 矩阵中的幸运数
4 分 - 设计一个支持增量操作的栈
4 分 - 将二叉搜索树变平衡
6 分 - 最大的团队表现值

展开讨论

想先继承TreeNode加个height属性,然后层次遍历边插入边调整,但是报错了,也不知道哪错了
为什么会出这个错?我没传TreeNode进insert函数里啊,tree也是Node类型的啊?
报错信息:

solution.cpp: In function ‘int getBalance(Node*)’:
Line 33: Char 25: error: invalid conversion from ‘TreeNode*’ to ‘Node*’ [-fpermissive]
     return height(root->left) - height(root->right);
                   ~~~~~~^~~~
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
struct Node:TreeNode
{
    int height;
    Node(int x):TreeNode(val)
    {
        height = 1;
    }
};

int height(Node *root)
{
    if(root == NULL) return 0;
    return root->height;
}
int getBalance(Node *root)    //获得以root为根的子树的平衡因子 
{
    if(root == NULL)  return 0;
    return height(root->left) - height(root->right);
}
/*
     y                               x
    / \     Right Rotation          /  \
   x   T3   - - - - - - - >        T1   y 
  / \     < - - - - - - -            / \
T1  T2     Left Rotation            T2  T3
*/

Node* leftRotation(Node *x)
{//左单旋(左边矮),又称RR旋转(在较高的右子树的右子树插入结点导致失去平衡 ) 
    Node* y = x->right;
    x->right = y->left;
    y->left = x;
    
    //更新x,y的高度,必须先x,后y,因为x是y的子树 
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;
    
    return y;	//返回调整后的根结点 
} 
Node* rightRotation(Node *y)
{ //右单旋(右边矮),又称LL旋转(在较高的左子树的左子树插入结点导致失去平衡) 
    Node *x = y->left;
    y->left = x->right;
    x->right = y;
    
    //更新x,y的高度,必须先y,后x,因为y是x的子树 
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
    
    return x; 	//返回调整后的根结点 
} 
Node* insert(Node *root,int key)
{
    if(root == NULL)
    {
        return new Node(key);
    } 
    
    if(key < root->key)
    {
        root->left = insert(root->left, key); 
    }
    else if(key > root->key)
    {
        root->right = insert(root->right, key);
    }
    else 	//key == root->key不插入 
    {
        return root;
    }
    
    root->height = 1 + max(height(root->left),height(root->right));
    
    int balance = getBalance(root);		//检查平衡因子
    
    //LL情况 -->右单旋 
    if(balance > 1 && getBalance(root->left) >= 0)
    {//LL ---> 右单旋 
        return rightRotation(root); 
    } 
    
    if(balance > 1 && getBalance(root->left) < 0)
    {//LR ----->先左单旋后右单旋
        root->left = leftRotation(root->left);
        return rightRotation(root); 
    } 
    
    if(balance < -1 && getBalance(root->right) <= 0)
    {//RR---->左单旋
        return leftRotation(root);		
    }
    
    if(balance < -1 && getBalance(root->right) > 0)
    {//RL---->先右单旋后左单旋 
        root->right = rightRotation(root->right);
        return leftRotation(root);
    }
    return root;	//没有失去平衡 
}
class Solution {
public:
    TreeNode* balanceBST(TreeNode* root) {
        Node* tree = NULL;
        queue<TreeNode*>q;
        q.push(root);
        while(!q.empty())
        {
            TreeNode* cur = q.front();  q.pop();
            tree = insert(tree, cur->val);
            if(cur->left != NULL) q.push(cur->left);
            if(cur->right != NULL) q.push(cur->right); 
        }
        return tree;
    }
};

上面代码抄了一部分之前的学AVL树时的代码,下面有LL,LR,RR,RL情况的总结

详见:https://blog.csdn.net/qq_40691051/article/details/102923518

定义以自底向上第一个平衡因子为2或者-2为根的树为最小不平衡AVL树。那么它不平衡的原因就四种:
设根为root,这四种情况是:

情况 说明 平衡因子特点 解决办法
LL root的左子树比右子树高2,并且左子树的左子树比右子树高1或相等(插入时不会,删除时可能会) 此时root的平衡因子为2,左子树的平衡因子为1或0 右单旋
LR root的左子树比右子树高2,并且左子树的右子树比左子树高1(其实相等也可以,但我把相等的情况放上面去了) 此时root的平衡因子为2,左子树的平衡因子为-1 先左单旋后右单旋
RR root的右子树比左子树高2,并且右子树的右子树比左子树高1或相等(与LL同理) 此时,root的平衡因子为-2,右子树的平衡因子为-1或0 左单旋
RL root的右子树比左子树高2,并且右子树的左子树比右子树高1 此时,root的平衡因子为-2,root的右子树平衡因子为1 先右单旋后左单旋
展开全部 31 讨论