程序员面试金典——4.1二叉树平衡检查-CSDN博客

本文介绍了两种判断二叉树是否平衡的有效方法。第一种方法使用两次递归分别计算左子树和右子树的深度；第二种方法源自《剑指offer》，通过优化减少重复计算，提高效率。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Solution1：

转载自：https://www.nowcoder.com/profile/7699453/codeBookDetail?submissionId=15222689
这种用两个递归的方法还是第一次见，重点学习下depth的写法！
20181010整理代码

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

class Balance {
public:
    bool isBalance(TreeNode* root) {
        // write code here
        if(root == NULL)
            return true;
        int diff = depth(root->left) - depth(root->right);
        if(abs(diff) > 1)
            return false;
        else
            return isBalance(root->left) 
                   && isBalance(root->right);
    }
    
     int depth(TreeNode *root) {
        if(!root)
            return 0;
        int left = depth(root->left);
        int right = depth(root->right);
        return max(left, right) + 1;
    }
};

原答案

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

class Balance {
public:
    bool isBalance(TreeNode* root) {
        // write code here
        if(root == NULL)
            return true;
        int diff = depth(root->left) - depth(root->right);
        if(abs(diff) > 1)
            return false;
        else
            return true;
        return isBalance(root->left) && isBalance(root->right);
    }
    
     int depth(TreeNode *root) {
        if(root == NULL)
            return 0;
        int left = depth(root->left);
        int right = depth(root->right);
        return (left > right)? (left + 1):(right + 1);
    }
};