JZ39-平衡的二叉树

方法一
首先明确平衡二叉树的定义，即左子树的高度与右子树的高度差的绝对值不大于1，因此此题的关键在于如何求左右子树的高度，这里采用递归的写法，如果该节点为空，高度为0；否则该以该节点为根节点的子树的高度为其左子树的高度和右子树高度中较大值加1；然后判断是否是平衡二叉树就简单了，以root为根节点，如果root为空，则是空树，返回true；如果不为空，求出其左右子树的高度，根据平衡二叉树的定义，如果高度差的绝对值不大于1，返回true；否则返回false

public boolean IsBalanced_Solution(TreeNode root) {
    if(root == null) return true;
    int balanceFactor = Math.abs(getHeight(root.left) - getHeight(root.right));
    if(balanceFactor <= 1) return true;

    return false;
}

private int getHeight(TreeNode node){
    if(node == null)
        return 0;
    return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}

方法二
方法一思路简单，但存在一个问题，就是在求以root为根节点的左右子树的高度时，会递归调用求出所有子树的高度，只是没有将这些子树高度值保存下来；可以想见的是：如果子树已经不满足平衡二叉树的定义了，那自底向上求高度时，子树的上一层也必然不满足平衡二叉树定义，这也就是为什么方法一只判断根节点的左右子树高度差就可以。但实际在求子树高度时，如果子树已经不满足平衡二叉树的定义，就返回-1，且不再递归求解，反之，递归求解出子树高度。

public boolean IsBalanced_Solution(TreeNode root) {

    return getHeight(root) != -1;
}

private int getHeight(TreeNode node){
    if(node == null)
        return 0;
    int lHeight = getHeight(node.left);
    if(lHeight == -1) return -1;
    int rHeight = getHeight(node.right);
    if(rHeight == -1) return -1;
    int balanceFactor = Math.abs(lHeight - rHeight);
    if(balanceFactor > 1) return -1;
    return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}