检查二叉树平衡性
实例要求
- 1、实现一个函数,检查二叉树是否平衡;
- 2、在这个问题中,平衡树的定义如下:
任意一个节点,其两棵子树的高度差不超过 1
;
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
实例分析
- 1、利用递归遍历二叉树的每个节点,计算其左右子树的高度差是否小于等于 1;
- 2、如果是则继续递归地检查左右子树是否平衡,直到叶子节点或者某个节点的子树不平衡为止;
- 3、最终返回整棵树是否平衡的结果。
示例代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
// 计算节点的高度
int height(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
int left_height = height(root->left);
int right_height = height(root->right);
return (left_height > right_height ? left_height : right_height) + 1;
}
// 检查二叉树是否平衡的辅助函数
bool isBalancedUtil(struct TreeNode* root) {
if (root == NULL) {
return true;
}
int left_height = height(root->left);
int right_height = height(root->right);
if (abs(left_height - right_height) <= 1 && isBalancedUtil(root->left) && isBalancedUtil(root->right)) {
return true;
}
return false;
}
// 检查二叉树是否平衡的主函数
bool isBalanced(struct TreeNode* root) {
return isBalancedUtil(root);
}
代码解释
- 1、
height(struct TreeNode* root)
: 这个函数计算给定节点 root 的高度(或深度)。它通过递归地计算左子树和右子树的高度,然后返回较大的高度加上 1,表示当前节点的高度; - 2、
isBalancedUtil(struct TreeNode* root)
: 这是一个辅助函数,用来检查以 root 为根的子树是否平衡。它通过递归地检查左子树和右子树的高度差是否小于等于 1,并且左子树和右子树是否也是平衡的,来判断当前子树是否平衡; - 3、
isBalanced(struct TreeNode* root)
: 这是主函数,用来检查整棵二叉树是否平衡。它调用了 isBalancedUtil 函数来递归地检查每个子树是否平衡,并返回最终的判断结果;
运行结果