判断二叉树是否为平衡二叉树
平衡二叉树的递归定义: (1)空树。 (2)他的左子树和右子树都是平衡二叉树，并且左子树和右子树的高度差的绝对值不会超过1(<=1)。
根据平衡二叉树的定义，可以很容易的判断一棵二叉树是否为平衡二叉树，首先是空树，满足条件。如果不是空树，需要检验它的两棵子树高度差的绝对值，这里需要一个辅助程序，求解一棵二叉树的高度。如果不满足条件(2)即不是平衡二叉树，如果满足，递归的判断其左右子树是否同时满足为平衡二叉树的条件。
代码实现:
struct node {
int val;
node *left, *right;
};
int height(node *root) {
if (!root) return 0;
int left = height(root->left);
int right = height(root->right);
return max(left, right) +1;
}
bool isAVL(node *root) {
if (!root) return 1;
if (abs(height(root->left)-height(root->right)) >1) return 0;
return isAVL(root->left) && isAVL(root->right);
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读