110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees ofeverynode never differ by more than 1.

思路： 用-1避免不必要的搜索

public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root==null) return true;
        int totalheight = height(root);
        return totalheight!=-1;
    }

    public int height(TreeNode root){
        if (root==null) return 0;

        int lH = height(root.left);
        if (lH==-1) return -1;

        int rH = height(root.right);
        if (rH==-1) return -1;

        if (Math.abs(lH-rH)>1){
            return -1;
        }

        return Math.max(lH,rH)+1;
    }
}