剑指offer 平衡二叉树 Java

题目

 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

---

题解

 直接递归即可

public class Solution {
    boolean isBalanced = true;
    public boolean IsBalanced_Solution(TreeNode root) {
        depth(root);
        return isBalanced;
    }
    public int depth(TreeNode root){
        if(root == null) return 0;
        int left = depth(root.left);
        int right = depth(root.right);
        if(left - right>1||right - left>1) isBalanced = false;
        return left>right?left+1:right+1;
    }
}

 上面的方法会出现重复计算，当我们判断到已经不平衡时无需再进行计算，直接返回特定值即可。

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        int isBalanced = depth(root);
        return isBalanced==-1?false:true;
    }
    public int depth(TreeNode root){
        if(root == null) return 0;
        int left = depth(root.left);
        if(left == -1) return -1;
        int right = depth(root.right);
        if(right == -1) return -1;
        if(left - right>1||right - left>1){
            return -1;
        }
        else return left>right?left+1:right+1;
    }
}