8ms C solution complexity O(n)


  • 2
    U
    #define MAX(a,b) ((a>b)?a:b)
    int __isBalanced(struct TreeNode* root) {
        
        int left, right, diff;
        
        if (!root)
            return 0;
        
        right = __isBalanced(root->right);
        left = __isBalanced(root->left);
        if (right == -1 || left == -1)
            return -1;
            
        diff = (right > left) ? right - left : left -right;
        if (diff > 1)
            return -1;
        else 
            return 1 + MAX(left, right);
            
    }
    
    bool isBalanced(struct TreeNode* root) {
        return !(__isBalanced(root) == -1);
    }

  • -1
    L
     int max(int a, int b)
    {
         return (a >= b)? a: b;
    }
    int height(TreeNode* node)
    {
        if(node == NULL)
            return 0;
        return 1 + max(height(node->left), height(node->right));
    } 
    bool isBalanced(TreeNode* root) {
        int lh;
        int rh;  
        if(root == NULL)
            return true; 
        lh = height(root->left);
        rh = height(root->right);
    
        if( abs(lh-rh) <= 1 && isBalanced(root->left) && isBalanced(root->right))
            return true;
    
        return false;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.