LeetCode-1382。平衡二叉搜索树

Question

struct TreeNodeC {
    int val;
    int height;
    struct TreeNodeC *left;
    struct TreeNodeC *right;
};

struct TreeNodeC *avl = NULL;

int check_balance_factor(struct TreeNodeC *root) {
    int balance_factor = 0;
    if (root->left == NULL && root->right == NULL) {
        balance_factor = 0;
    } else
    if (root->left == NULL && root->right != NULL) {
        balance_factor = (root->right)->height;
    } else
    if (root->left != NULL && root->right == NULL) {
        balance_factor = (root->left)->height;
    } else {
        balance_factor = ((root->left)->height) - ((root->right)->height);
        balance_factor = (balance_factor >= 0) ? (balance_factor) :(balance_factor * (-1));
    }
    return balance_factor;
}

struct TreeNodeC *heightImbalancingNode(struct TreeNodeC *root, bool *isFound) {
    struct TreeNodeC *TempB = NULL;
    if (root != NULL) {
        TempB = heightImbalancingNode(root->right, isFound);
        if ((*isFound) == false) {
            int bal_f = check_balance_factor(root);
            if (bal_f > 1) {
                *isFound = true;
                TempB = root;
                return TempB;
            }
        }
    }
    return TempB;
}

struct TreeNodeC *LLRotation(struct TreeNodeC *root, int val) {
    int val_temp = root->val;
    struct TreeNodeC *TempZ = (struct TreeNodeC *)malloc(sizeof(struct TreeNodeC));
    TempZ->val = root->val;
    TempZ->left = root->left;
    TempZ->right = root->right;
    TempZ->height = root->height;
    struct TreeNodeC *Temp = root->right;
    struct TreeNodeC *TempA = Temp->left;
    Temp->left = TempZ;
    (Temp->left)->right = TempA;
    if (val_temp == val) {
        avl = Temp;
    } else {
        *root = *Temp;
    }
    return Temp;
}

int maximum(int a, int b) {
    if (a > b) {
        return a;
    }
    return b;
}

int height(struct TreeNodeC *root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + maximum(height(root->left), height(root->right));
}

int updateHeight(struct TreeNodeC **root) {
    if (*root == NULL) {
        return 0;
    }
    (*root)->height = height((*root));
    updateHeight(&((*root)->left));
    updateHeight(&((*root)->right));
    return 0;
}

struct TreeNodeC *createNode(int val) {
    struct TreeNodeC *newNode = (struct TreeNodeC *)malloc(sizeof(struct TreeNode));
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->val = val;
    return newNode;
}

struct TreeNodeC *insertion(int val, struct TreeNodeC *root) {
    struct TreeNodeC *Temp = root;
    if (Temp == NULL) {
        struct TreeNodeC *newNode = createNode(val);
        return newNode;
    }
    while (1) {
        if (val < Temp->val) {
            if (Temp->left == NULL) {
                struct TreeNodeC *newNode = createNode(val);
                Temp->left = newNode;
                return root;
            }
            Temp = Temp->left;
        } else {
            if (Temp->right == NULL) {
                struct TreeNodeC *newNode = createNode(val);
                Temp->right = newNode;
                return root;
            }
            Temp = Temp->right;
        }
    }
}

struct TreeNodeC *avlTreeInsertion(int val) {
    bool isFound = false;
    avl = insertion(val, avl);
    updateHeight(&avl);
    struct TreeNodeC *ll = heightImbalancingNode(avl, &isFound);
    if (isFound) {
        struct TreeNodeC *rotated = LLRotation(ll, avl->val);
        return avl;
    }
    return avl;
}

void inOrderTraversal(struct TreeNode *root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        avlTreeInsertion(root->val);
        inOrderTraversal(root->right);
    }
}
struct TreeNodeC *balanceBST(struct TreeNode *root) {
    inOrderTraversal(root);
    return avl;
}

我写了这段代码来平衡二叉搜索树的高度。该解决方案工作正常。在 leet 代码中，我得到了 Time limit Exceeded for larger inputs。有人可以帮助我在哪里可以更好地克服 TLE 错误。请不要 post 一个全新的解决方案来解决这个问题。我希望用我采用的方法解决问题，但时间复杂度更高

Answer 1


 
struct TreeNodeC* balanceBST(struct TreeNode* root){    
    struct TreeNodeC
{
     int val;
     int height;
     struct TreeNodeC *left;
     struct TreeNodeC *right;
 };
    struct TreeNodeC* avl=NULL;
    int check_balance_factor(struct TreeNodeC * root)
{
    int balance_factor = 0;
    if(root->left==NULL && root->right==NULL)
    {
        balance_factor = 0;
    }
    else if(root->left==NULL && root->right!=NULL)
    {
        balance_factor =  (root->right)->height;
    }
    else if(root->left!=NULL && root->right==NULL)
    {
        balance_factor = (root->left)->height;
    }
    else
    {
        balance_factor =((root->left)->height) - ((root->right)->height);
        balance_factor=(balance_factor>=0)?(balance_factor):(balance_factor*(-1));
    }
    return balance_factor;
}   
struct TreeNodeC* heightImbalancingNode(struct TreeNodeC* root,bool* isFound)
{
          struct TreeNodeC* Temp=NULL; 
        if(root!=NULL)
        {    
            Temp= heightImbalancingNode(root->right,isFound);
            if((*isFound)==false)
            {
            int bal_f=check_balance_factor(root); 
                if(bal_f>1)
                {
                *isFound=true;
                Temp=root;
                return Temp;
                }
            }
        }
        return Temp;      
}
    void LLRotation(struct TreeNodeC* root,int val){
        int val_temp=root->val;
        struct TreeNodeC* TempZ=(struct TreeNodeC* )malloc(sizeof(struct TreeNodeC));
        TempZ->val=root->val;
        TempZ->left=root->left;
        TempZ->right=root->right;
        TempZ->height=root->height;
        struct TreeNodeC* Temp=root->right;
        struct TreeNodeC* TempA=Temp->left;
        Temp->left=TempZ;
        (Temp->left)->right=TempA; 
        if(val_temp==val){
           avl=Temp; 
        }
        else{
            *root=*Temp;
        }    
}
    int maximum(int a,int b)
    {
        if(a>b){
            return a;
        }
        return b;
    }
    int updateHeight(struct TreeNodeC* root)
    {
        if(root==NULL)
        {
            return 0;
        }
        root->height= 1+maximum(updateHeight(root->left),updateHeight(root->right));
        return root->height;
       
    }
    struct TreeNodeC* createNode(int val)
    {
        struct TreeNodeC* newNode=(struct TreeNodeC*) malloc(sizeof(struct TreeNode));
        newNode->left=NULL;
        newNode->right=NULL;
        newNode->val=val;
        return newNode;
    }
   
     struct TreeNodeC* insertion(int val,struct TreeNodeC* root)
     {
       struct TreeNodeC* Temp=root; 
        if(Temp==NULL){
            struct TreeNodeC* newNode=createNode(val);
            return newNode;    
    }
       while(1)
       {
           if(val<Temp->val)
           { 
               if(Temp->left==NULL)
               {
                   struct TreeNodeC* newNode=createNode(val);
                   Temp->left=newNode;
                   return root;
               }
               Temp=Temp->left;
           }
           else{
              
               if(Temp->right==NULL){
                   struct TreeNodeC* newNode=createNode(val);
                   Temp->right=newNode;
                   return root;
               }
                Temp=Temp->right;
           }
       }
    }
   void avlTreeInsertion(int val)
   {
       bool isFound=false;
       avl= insertion(val,avl);
        updateHeight(avl);
       struct TreeNodeC* ll= heightImbalancingNode(avl,&isFound);
       if(isFound){
        LLRotation(ll,avl->val);
       }
   }
  void inOrderTraversal(struct TreeNode* root){
      if(root!=NULL){
      inOrderTraversal(root->left);  
      avlTreeInsertion(root->val);
      inOrderTraversal(root->right);
      }   
  }    
   inOrderTraversal(root);
    return avl;      
}

对程序做了一些小改动。正在运行

LeetCode-1382。平衡二叉搜索树

LeetCode-1382. Balance a Binary Search Tree

c

binary-tree

avl-tree