判断二叉树是否是平衡二叉树

二叉树的节点定义为

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

二叉树的深度：根节点到叶节点的最长路径长度
平衡二叉树：二叉树中任一节点的左右子树的深度相差不超过1

递归的方法代码如下：

    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;        
        }

        int left = getHeight(root.left);
        int right = getHeight(root.right);
        if(Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right))
            return true;

        return false;
    } 

    public int getHeight(TreeNode node){
        if(node == null)
            return 0;
        int left = getHeight(node.left);
        int right = getHeight(node.right);

        return Math.max(left, right)+1;
    }

上述方法有很多的重复计算，性能不是很好。是否能实现每个节点只遍历一次呢，
可利用后序遍历的方法，在遍历每个节点的时候我们已经遍历了它的左右子树，且记录下其深度

    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;        
        }

        int depth = 0;
        return isBal(root, &depth);
    } 

    public boolean isBal(TreeNode node, int* depth){
        if(node == null){
            *depth = 0;
            return true;
        }

        int left;
        int right;
        if(isBal(node.left, &left) && isBal(node.right, &right)){
            if(Math.abs(left - right) < 2)
                return true;
        }       
        return false;
    }