同样,使用递归算法写出判断二叉树是否是平衡二叉树
时间: 2025-02-12 16:27:53 浏览: 46
判断一棵二叉树是否是平衡二叉树,通常也采用递归的方式来实现。平衡二叉树是指任意节点的两个子树的高度差不超过1。下面是一个简单的C语言递归函数示例:
```c
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 辅助函数用于获取节点高度
int height(TreeNode *root) {
if (root == NULL) return 0;
return 1 + MAX(height(root->left), height(root->right));
}
// 主函数:判断是否为平衡二叉树
int isBalanced(TreeNode *root) {
if (root == NULL) return 1; // 空树视为平衡
int left_height = height(root->left);
int right_height = height(root->right);
if (abs(left_height - right_height) <= 1 && isBalanced(root->left) && isBalanced(root->right)) {
return 1; // 如果满足条件,返回1表示平衡
} else {
return 0; // 否则返回0表示不平衡
}
}
```
上面的`isBalanced`函数先计算当前节点的左右子树高度,然后检查它们的差的绝对值是否小于等于1,同时递归判断左右子树是否都是平衡的。如果所有条件都成立,那么这棵树就是平衡的。
阅读全文
相关推荐















