[二叉树]！110. Balanced Binary Tree

题目：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 of every node never differ by more than 1.

判定一个二叉树是否是平衡二叉树。
即二叉树所有子树深度差别都不超过1。

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int l = Depth(root.left);
        int r = Depth(root.right);
        if( l<0 || r<0 || Math.abs(l-r)>1) return false;
        else return true;
        
    }
    public int Depth(TreeNode node){
        if(node == null) return 0;
        int l = 0, r = 0;
        if(node.left != null) l = Depth(node.left);
        if(node.right != null) r = Depth(node.right); 
        if( l<0 || r<0 || Math.abs(l-r)>1) return -1; //即该节点root下的子树已经不平衡了
        else return Math.max(l,r) + 1;     //如果左右子树是平衡的，那么返回深度＋1
    }
}