对二叉树有困惑的小伙伴可以看一下我之前的文章

二叉树一_染柒_GRQ的博客-CSDN博客

二叉树二_染柒_GRQ的博客-CSDN博客

二叉树三_染柒_GRQ的博客-CSDN博客

点击上方链接即可查看。

题目

110. 平衡二叉树 - 力扣LeetCode

注意事项

首先我们要注意到该题的意思是所有节点的高度差不超过一而不是只有根节点的高度差不超过一例如

错误示例

上图显然不符合题目要求。

那么我们再来思考一下如果树为空的情况显然是符合题目要求的。

实现代码

根据上面的意思转换为代码就是这样

bool isBalanced(struct TreeNode* root)
{
    if(root == NULL)
    {
        return true;
    }
}

但是这样显然不够只是判断了树为空的情况。

那么我们在树非空的情况下要想判断是否为平衡树最好的方法是写一个计算树深度的函数。

我找到一个题目专门计算深度的感兴趣的可以看一下哦

题目104. 二叉树的最大深度 - 力扣LeetCode

那么我们把计算深度的函数解决了就顺便解决了上题。

其实我们在学习二叉树的时候写过一个计数函数大家可以参考一下

参考文献二叉树三_染柒_GRQ的博客-CSDN博客

//法三
int TreeSize(BTDNode* root)
{
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

这里是计算节点和左右子树之和而本题是要计算左子树与右子树的差所以我们在写代码的时候只要写左子树加节点 或者 右子树加节点就行了。

当然这里不推荐三目运算符比较麻烦。

//计算深度
int maxDepth(struct TreeNode* root)
{
    if(root ==  NULL)
    {
        return 0;
    }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return leftDepth > rightDepth ? leftDepth + 1: rightDepth + 1;
}

leftDepth 和rightDepth 是为了避免在递归过程中被替换掉。

最后我们在进行比较就行了。

bool isBalanced(struct TreeNode* root)
{
    if(root == NULL)
    {
        return true;
    }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    //比较
    return abs(leftDepth - rightDepth) < 2
    && isBalanced(root->left)
    && isBalanced(root->right);
}

注意”abs“是计算绝对值的函数。

总结

本题主要是对二叉树知识的运用如果仍有疑问应该及时对二叉树中的知识点进行复习和巩固当然大家也可以点击主页里面有详细的二叉树教程文章。

欢迎大家点赞和评论。