【数据结构与算法经典例题】判断一颗二叉树是否是平衡二叉树

用户11396077

发布于 2024-12-06 19:28:30

1120

文章被收录于专栏：C/C++指南

一、问题描述

给定一个二叉树，判断它是否是平衡二叉树平衡二叉树（Balanced Binary Tree）是一种特殊的二叉树，其中任一节点的左、右两个子树的高度差的绝对值不超过1，并且左、右两个子树都是一棵平衡二叉树。 原题出自 110. 平衡二叉树 - 力扣（LeetCode）

二、解题思路

解题思路： 判断平衡二叉树需要计算二叉树的高度，所以定义一个辅助函数，用于计算二叉树的高度。这个函数会递归地调用自身来计算左子树和右子树的高度，然后返回两者中的较大值加1（加上根节点的高度）。更多细节可以参考下面这篇二叉树详解文章 【数据结构与算法】详解二叉树下：实践篇————通过链式结构深入理解并实现二叉树-CSDN博客

在主函数中，使用递归的方式遍历二叉树的每一个节点。对于每个节点，先判断其是否为空树，或者左右子树为空，这两种情况都可以直接判定是平衡的。
之后判定其左子树和右子树是否都是平衡二叉树，然后计算左子树和右子树的高度差，如果高度差的绝对值大于1，则返回false，表示这棵树不是平衡二叉树。
递归调用左子树和右子树，如果都满足平衡二叉树的条件，则返回true。

三、C语言实现代码

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    
};
typedef struct TreeNode TNode;
int TreeHeight(TNode* root)//求树的高度子函数
{
    if (root == NULL)
        return 0;
    int leftHeight = TreeHeight(root->left);
    int rightHeight = TreeHeight(root->right);
    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
bool isBalanced(struct TreeNode* root) //判断是否平衡
{
    if (root == NULL)
        return true;
    int leftHeight = TreeHeight(root->left);
    int rightHeight = TreeHeight(root->right);
    if (abs(leftHeight - rightHeight) > 1)//如果左右子树相差大于1，返回false
        return false;
    return isBalanced(root->left) && isBalanced(root->right);//否则对左右子树递归判断
}