c语言递归判断平衡二叉树排序树
时间: 2023-10-03 11:09:18 浏览: 47
C语言递归判断平衡二叉树和排序树的方法与Python相同,只是语法略有不同。下面是C语言实现的代码:
```c
#include <limits.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int get_height(struct TreeNode *node) {
if (!node) {
return 0;
}
int left_height = get_height(node->left);
int right_height = get_height(node->right);
return left_height > right_height ? left_height + 1 : right_height + 1;
}
bool isBST(struct TreeNode *node, long long min_val, long long max_val) {
if (!node) {
return true;
}
if (node->val <= min_val || node->val >= max_val) {
return false;
}
return isBST(node->left, min_val, node->val) && isBST(node->right, node->val, max_val);
}
bool isBalanced(struct TreeNode* root){
if (!root) {
return true;
}
int left_height = get_height(root->left);
int right_height = get_height(root->right);
if (abs(left_height - right_height) > 1) {
return false;
}
return isBalanced(root->left) && isBalanced(root->right) && isBST(root->left, INT_MIN, root->val) && isBST(root->right, root->val, INT_MAX);
}
```
其中,`get_height`函数用于计算二叉树的高度,`isBST`函数用于判断是否为二叉排序树。`isBalanced`函数是递归判断平衡二叉树的主函数。注意在判断是否为二叉排序树时,使用`INT_MIN`和`INT_MAX`来代替Python中的`float('-inf')`和`float('inf')`。