《剑指offer》 第55-2题 判断平衡二叉树（其实是判断树是否平衡）

首先搞清楚意思，本题的重点在于树是否平衡，左右子树的深度不超过1。而不关注于是否将其排序，成为平衡二叉搜索树。因此在只考虑平衡的情况下解题。

思路1：（由二叉树的深度的解法转换过来（55-1题就是求二叉树深度））
在使用递归求的深度后，其实可以在递归中，直接判断左右子树的差值。这时候就相当于多一个变量。

public class Solution {
    boolean isBalanced=true;//用于判断的变量
    public boolean IsBalanced_Solution(TreeNode root) {
        TreeDepth(root);
        return isBalanced;
    }

    public int TreeDepth(TreeNode root) {
        if(root==null)
            return 0;
        int left=TreeDepth(root.left);
        int right=TreeDepth(root.right);
        if(left-right>1 || right-left>1)
            isBalanced=false;
        return left>right?left+1:right+1;
    }
}

思路2 上述做法的缺点是，当在某个子树不满足条件，被判断不是平衡二叉树后，还会进行很多次计算，直到计算到根节点的最大深度为止。这是因为上面的做法需要遍历所有的节点。因此使用剪枝。
给出大佬的写法

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return getDepth(root) != -1;
    }

    private int getDepth(TreeNode root) {
        if (root == null) return 0;
        int left = getDepth(root.left);
        if (left == -1) return -1;
        int right = getDepth(root.right);
        if (right == -1) return -1;
        return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
    }
}

根据大佬的思路，将思路1的写法进行剪枝。其实就是多加两个判断，不符合条件的，直接一直向上返回，没必要还去计算深度。

public class Solution {
    boolean isBalanced=true;
    public boolean IsBalanced_Solution(TreeNode root) {
        TreeDepth(root);
        return isBalanced;
    }

    public int TreeDepth(TreeNode root) {
        if(root==null)
            return 0;
        int left=TreeDepth(root.left);
        if (left == -1) return -1;
        int right=TreeDepth(root.right);
        if (right == -1) return -1;
        if(left-right>1 || right-left>1){
            isBalanced=false;
            return -1;
           }    
        return left>right?left+1:right+1;
    }
}