• 判断是否为平衡二叉树

判断是否为平衡二叉树

public boolean isBalanced(TreeNode root) {
    return dfs(root) != -1;
}

public int dfs(TreeNode node){
    if(node == null) return 0;  //node为空，直接返回0，终止条件

    int left = dfs(node.left);
    if(left == -1) return -1;  

    int right = dfs(node.right);
    if(right == -1) return -1;

    //right-left的绝对值超过一，则肯定不是平衡二叉树，我们这里规定返回-1来表示，也可以是-2，-3等
    return Math.abs(right-left) > 1 ? -1 : (right > left ? right : left)+ 1;
}