【LeetCode】110. Balanced Binary Tree

LeetCode-110

Links:https://leetcode.com/problems/balanced-binary-tree/

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

思路：递归深度判断即可.（需另写深度计算函数）

解法1：计算二叉树的深度

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int getDepth(TreeNode* root)
    {
        if(root==NULL)return 0;
        else{
            return max(getDepth(root->left),getDepth(root->right))+1;
        }
    }
    bool isBalanced(TreeNode* root) {
        if(root == NULL)return true;
        int left = getDepth(root->left);
        int right = getDepth(root->right);
        if((left==0&&right==1)||(right==0&&left==1))return true;
        if(left-right>1 || right-left>1)return false;
        else return isBalanced(root->left)&&isBalanced(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) {}

* };

class Solution {

public:

int getDepth(TreeNode* root)

{

if(root==NULL)return 0;

else{

return max(getDepth(root->left),getDepth(root->right))+1;

}

bool isBalanced(TreeNode* root) {

if(root == NULL)return true;

int left = getDepth(root->left);

int right = getDepth(root->right);

if((left==0&&right==1)||(right==0&&left==1))return true;

if(left-right>1 || right-left>1)return false;

else return isBalanced(root->left)&&isBalanced(root->right);

}

};

解法2：计算平衡二叉树的深度，非平衡二叉树返回-1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int BalancedDepth(TreeNode* root){
        if(root==NULL)return 0;
        int l = BalancedDepth(root->left);
        int r = BalancedDepth(root->right);
        if(l<0 || r<0 || abs(l-r)>1)return -1;
        else return max(l,r)+1;
    }
    
    bool isBalanced(TreeNode* root) {
        if(BalancedDepth(root)>=0)return true;
        else return false;
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

int BalancedDepth(TreeNode* root){

if(root==NULL)return 0;

int l = BalancedDepth(root->left);

int r = BalancedDepth(root->right);

if(l<0 || r<0 || abs(l-r)>1)return -1;

else return max(l,r)+1;

}

bool isBalanced(TreeNode* root) {

if(BalancedDepth(root)>=0)return true;

else return false;

}

};

下面附上一个12ms的解法：我至今不知道为何是12ms…因为你稍微改一下格式比如去掉public下面的换行，就变成16ms了…

class Solution {
private:  
    int depth(TreeNode* root) {
        if (root == NULL) {
            return 0;
        } else {
           int left_depth = depth(root->left);
           int right_depth = depth(root->right);
           if (left_depth == -1 || right_depth == -1 || (left_depth - right_depth > 1) || (left_depth - right_depth < -1)) 
                return -1;
           else if (left_depth - right_depth > 0) 
                return left_depth + 1;
           else return right_depth + 1;
        }
    }
public:

    bool isBalanced(TreeNode *root) {
        if (root == NULL) return true;
        else return (depth(root) !=-1);
    }
};

class Solution {

private:

int depth(TreeNode* root) {

if (root == NULL) {

return 0;

} else {

int left_depth = depth(root->left);

int right_depth = depth(root->right);

if (left_depth == -1 || right_depth == -1 || (left_depth - right_depth > 1) || (left_depth - right_depth < -1))

return -1;

else if (left_depth - right_depth > 0)

return left_depth + 1;

else return right_depth + 1;

}

public:

bool isBalanced(TreeNode *root) {

if (root == NULL) return true;

else return (depth(root) !=-1);

}

};

【LeetCode】110. Balanced Binary Tree

Tagged on: LeetCode