题解 | #判断是不是平衡二叉树（基础版）#

// 自顶向下，两个递归，第一个遍历所有节点，第二个获取子树的高度
// 时间复杂度O（n^2）,空间复杂度O（n）
public class Solution {
    public Integer height(TreeNode root){
        if (root == null){
            return 0;
        }
        if (height(root.right) < height(root.left))
            return height(root.left)+1;
        else
            return height(root.right)+1;
    }
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null)
            return true;
        if (!IsBalanced_Solution(root.left) || !IsBalanced_Solution(root.right)){
            return false;
        }
        Integer h_dif = height(root.right) - height(root.left);
        if (h_dif > 1 || h_dif < -1)
            return false;
        return true;
    }
}