如何用c语言判断左右子树高度差是否不超过1
时间: 2024-01-01 08:03:13 浏览: 57
可以使用递归实现。首先定义一个函数来计算子树的高度,然后比较左右子树的高度差,如果小于等于1,则该子树是平衡的。然后递归判断左右子树是否也是平衡的。
代码示例:
```
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int height(struct TreeNode* root) {
if (root == NULL) return 0;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
bool isBalanced(struct TreeNode* root) {
if (root == NULL) return true;
if (abs(height(root->left) - height(root->right)) > 1) return false;
return isBalanced(root->left) && isBalanced(root->right);
}
```
当然,这只是一种实现方式,还可以使用其他方法来判断左右子树的高度差是否超过1,比如在递归的同时记录树的高度,在比较左右子树高度之前先判断左右子树是否平衡等。
阅读全文