110. 平衡二叉树
题解:这道题目我走了一个误区,我以为的是平衡二叉树是只要保证根节点的左右子树高度之差在<=1,但是平衡二叉树是每个节点的左右子树高度之差都保证在<=1。所以我们的思路就是先递归每个节点,求出其左右子树的高度之差,如果不符合,则返回一个-1,表示此树已经不符合平衡二叉树,如果符合
则返回此节点的高度。
class Solution {
public boolean isBalanced(TreeNode root) {
return getHeight(root)>=0;
}
public int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
//递归,求出当前节点左右子树的高度
int leftLength = getHeight(root.left);
int rightLength = getHeight(root.right);
//判断条件,如果符合则返回当前节点高度,否则返回-1,表示此树不是平衡二叉树
if (Math.abs(leftLength - rightLength) > 1 || leftLength == -1 || rightLength == -1) {
return -1;
}
return Math.max(leftLength, rightLength) + 1;
}
}