判断二叉树是否为平衡二叉树

lexingsen

发布于 2022-02-24 11:12:54

18000

代码可运行

文章被收录于专栏：乐行僧的博客乐行僧的博客

运行总次数：0

代码可运行

平衡二叉树的递归定义: (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);
}