解法一：自顶向下递归
自顶向下地判断各个结点。
判断某顶点为根结点的树是否为平衡二叉树，首先要满足的条件是：对于这个顶点，左子树的高度和右子树的高度之差的绝对值小于等于1。
其次：左子树为平衡二叉树，右子树也为平衡二叉树。
综上，自顶向下递归地检查每个顶点。
缺点：自顶向下计算每个结点的高度时存在大量冗余。
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if(Math.abs(leftHeight - rightHeight) > 1)
return false;
return isBalanced(root.left) && isBalanced(root.right);
}
private int getHeight(TreeNode root) {
if(root == null) return 0;
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
}
解法二：自底向上递归
自底向上递归地返回结点的高度。
递归的每一层要做的工作：根据向上返回得到的左右子结点的高度，判断是否平衡，若平衡，返回当前结点的高度（左右子节点高度的最大值加一）。若不平衡，则之后的高度都不必再计算了，这棵树必然不平衡，这种情况下向上返回-1。
递归结束后，若树是平衡的，将得到根结点的高度（不断通过返回的子结点的高度计算得到）；若树是不平衡的，将得到-1。根据这个结果返回true/false即可。
相对于解法一，这样做可以不断通过返回的子树高度计算当前结点高度，无需向解法一那样结点的高度会被重复计算。而且可以通过返回-1来指示树是不平衡的，提前结束结点高度的计算。
class Solution {
public boolean isBalanced(TreeNode root) {
return getHeight(root) != -1;
}
private int getHeight(TreeNode root) {
if(root == null) return 0;
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if(leftHeight == -1 || rightHeight == -1)
return -1;
if(Math.abs(leftHeight - rightHeight) > 1)
return -1;
return Math.max(leftHeight, rightHeight) + 1;
}
}
