给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1(利用c语言实现本题)
时间: 2024-04-12 15:27:04 浏览: 10
要判断一个二叉树是否是高度平衡的,我们可以使用递归的方法来解决。首先,我们需要实现一个函数来计算二叉树的高度。
```c
// 定义二叉树节点结构
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 计算二叉树的高度
int getHeight(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
```
接下来,我们可以实现一个函数来判断二叉树是否是高度平衡的。
```c
// 判断二叉树是否是高度平衡的
bool isBalanced(struct TreeNode* root) {
if (root == NULL) {
return true;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
if (abs(leftHeight - rightHeight) > 1) {
return false;
}
return isBalanced(root->left) && isBalanced(root->right);
}
```
以上代码中,我们首先判断根节点的左右子树的高度差是否大于1,如果大于1则返回false,表示不是高度平衡的。然后递归地判断左右子树是否都是高度平衡的。
希望以上代码能帮助到你!如果还有其他问题,请继续提问。