【数据结构与算法】判断一颗二叉树是否是平衡二叉树
【摘要】 给定一个二叉树，判断它是否是平衡二叉树。平衡二叉树（Balanced Binary Tree）是一种特殊的二叉树，其中任一节点的左、右两个子树的高度差的绝对值不超过1，并且左、右两个子树都是一棵平衡二叉树。
目录
一、问题描述
给定一个二叉树，判断它是否是 平衡二叉树
平衡二叉树（Balanced Binary Tree）是一种特殊的二叉树，其中任一节点的左、右两个子树的高度差的绝对值不超过1，并且左、右两个子树都是一棵平衡二叉树。
二、解题思路
解题思路：
判断平衡二叉树需要计算二叉树的高度，所以定义一个辅助函数，用于计算二叉树的高度。这个函数会递归地调用自身来计算左子树和右子树的高度，然后返回两者中的较大值加1（加上根节点的高度）。
- 在主函数中，使用递归的方式遍历二叉树的每一个节点。对于每个节点，先判断其是否为空树，或者左右子树为空，这两种情况都可以直接判定是平衡的。
- 之后判定其左子树和右子树是否都是平衡二叉树，然后计算左子树和右子树的高度差，如果高度差的绝对值大于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);//否则对左右子树递归判断
}
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）