平衡二叉树

问题描述：?

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点?的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

• 树中的节点数在范围?[0, 5000]?内
• -104 <= Node.val <= 104

解题思路：

由题意知，平衡二叉树是每棵树的左右子树高度差小于等于1，这里可以利用之前做过的树的最大深度解决，注意要涉及到每棵树。

//求树的最大深度
int maxDepth(struct TreeNode* root)
{
	if (root == NULL)
		return 0;
	int leftDepth = maxDepth(root->left);
	int rightDepth = maxDepth(root->right);
	//return maxDepth(root->left) > maxDepth(root->right) ? maxDepth(root->left)+1 : maxDepth(root->right) + 1;
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
//平衡二叉树
bool isBalanced(struct TreeNode* root)
{
	if (root == NULL)
		return true;
	int leftDepth = maxDepth(root->left);
	int rightDepth = maxDepth(root->right);
	//每一棵数都要平衡
	return abs(leftDepth - rightDepth) < 2 && isBalanced(root->left) && isBalanced(root->right);
}

小tip：如何销毁二叉树

注意传结构体指针的地址。

//销毁二叉树
void DestoryTree(struct TreeNode** root)
{
	if (root == NULL)
		return;
	DestoryTree(&(*root)->left);
	DestroryTree(&(*root)->right);
	free(*root);
	root == NULL;
}