题目描述
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例：
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
思路
1.根据平衡二叉树的定义可知，只要有一个结点它的左右子树深度相差超过1便不符合要求。
2.可以额外编写一个函数，用于计算一个结点的左右子树可以达到的深度，若深度差值符合要求，则一直递归下去，否则直接返回false即可。
Java代码实现
public boolean isBalanced(TreeNode root) {
if(root != null){
int leftDepth = treeDepth(root.left);
int rightDepth = treeDepth(root.right);
if(Math.abs(leftDepth-rightDepth) <= 1)
return isBalanced(root.left) && isBalanced(root.right);
return false;
}
return true;
}
private int treeDepth(TreeNode root){
if(root == null)
return 0;
return Math.max(treeDepth(root.left),treeDepth(root.right))+1;
}
