39. 平衡二叉树
题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
解题思路：
平衡二叉树：Wiki:在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)
我们可以通过递归的方式来获取二叉树每个节点的左右子树的深度，然后比较左右子树的深度，如果二者深度差值大于1，则可以判定该二叉树不是平衡二叉树，反之，该树为平衡二叉树。
如果从上向下进行判断，则会导致判断上层节点时，需要多次判断其下层节点。所以我们采用从下向上的方式进行判断，如果某节点出现左右子树深度差大于1，则可判定该树不是平衡二叉树。
解答：
class Solution {
public:
bool IsBalanced_Solution(TreeNode* pRoot) {
return TreeDepth(pRoot) != -1;
}
int TreeDepth(TreeNode* pRoot)
{
if(pRoot == nullptr)
return 0;
int leftDepth = TreeDepth(pRoot->left);
if(leftDepth == -1)
return -1;
int rightDepth = TreeDepth(pRoot->right);
if(rightDepth == -1)
return -1;
// 如果两子树深度差大于1，则该树不是平衡二叉树，返回-1做标志
return abs(leftDepth - rightDepth) > 1 ? -1 : max(leftDepth, rightDepth) + 1;
}
};
大家有兴趣可以访问我的个人博客，不定时更新一些内容哦！
图片来自必应壁纸
