解法一：递归1

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null) return true;
        return compare(root.left, root.right);
    }

    boolean compare(TreeNode p, TreeNode q){
        if(p!=null&&!compare(p.left, p.right)) return false;
        if(q!=null&&!compare(q.left, q.right)) return false;
        //if(p.val!=q.val) return false;
        return Math.abs(depth(p)-depth(q))<=1;
    }

    int depth(TreeNode root){
        return root==null? 0:Math.max(depth(root.left), depth(root.right))+1;
    }
}

解法二：递归2

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null) return true;
        if (Math.abs(depth(root.left)-depth(root.right))>1) return false;
        return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
    }

    int depth(TreeNode root){
        return root==null? 0:Math.max(depth(root.left), depth(root.right))+1;
    }
}

解法三：后序遍历

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return depth(root)!=-1;
    }
    int depth(TreeNode root){
        if(root==null) return 0;
        int l=depth(root.left);
        if(l==-1) return -1;
        int r=depth(root.right);
        if(r==-1) return -1;
        if(Math.abs(l-r)>1) return -1;
        return Math.max(l,r)+1;
    }
}