[编程题]平衡二叉树

方法一：最优解求解，通过后续遍历防止重复判断

/*
//offer原最优解算法解决
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return isBalance(root);
    }

    //并且利用后续遍历先判断左右子树是不是平衡二叉，再判断根节点
    public boolean isBalance(TreeNode root){
        if(root==null){
            return true;
        }
        int leftDepth=depth(root.left);
        int rightDepth=depth(root.right);
        if(isBalance(root.left)&&isBalance(root.right)){
            int differ=leftDepth-rightDepth;
                if(differ<=1&&differ>=-1){
                    return true;
                }
        }
        return false;
    }

    //求取树的深度
    public int depth(TreeNode root){
        if(root==null){
            return 0;
        }
        if(depth(root.left)>depth(root.right)){
            return depth(root.left)+1;
        }else{
            return depth(root.right)+1;
        }
    }
}

方法二：常规的递归解法，有重复判断

//单纯递归求解
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null){
            return true;
        }
        int leftDepth=depth(root.left);
        int rightDepth=depth(root.right);
        //先判断左子树和右子树之差成立吗
        if((leftDepth-rightDepth)>1||(leftDepth-rightDepth)<-1){
           return false;
        }else{
            //在判断左右子树分别是平衡二叉树吗
            return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
        }
    }

    //求取树的深度
    public int depth(TreeNode root){
        if(root==null){
            return 0;
        }
        if(depth(root.left)>depth(root.right)){
            return depth(root.left)+1;
        }else{
            return depth(root.right)+1;
        }
    }
}