平衡二叉树的判断，先序遍历，后序遍历的Java实现

解法1：
1.计算每个节点的高度
2.从根节点开始从上往下遍历，判断每个节点的左右子树是否是平衡的
思路简单。。。
缺点：每次遍历都要重新计算高度，很多节点的高度都重复计算了

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null)
            return true;
//先判断root节点满不满足平衡条件
        if(Math.abs(TreeDepth(root.left)-TreeDepth(root.right))>1)
            return false;
//在判断左右子树满不满足平衡条件，类似于二叉树的先根遍历
        return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
    }  
    public int TreeDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
    }

}

解法2：
从根节点开始，从上往下遍历，按照中序遍历的思想，从左右子节点向根节点遍历，一依次判断平衡状态，这样根结点可以重复利用已经计算的子节点的高度，只需要依次遍历整棵树。在遇到某个子树非平衡时，能直接结束，返回false。
实现1，这个实现比较巧妙，在遍历每层时创建一个临时变量，参考了C++实现，不过用到了引用传递，但我们都知道Java中Int类型变量传递过程中是值传递，所以创建了一个封装数值的对象。
完整代码如下：

class Num{
    int val;
}
public class Solution {
    boolean IsBalanced_Solution(TreeNode  pRoot) {
        Num depth=new Num();
        return IsBalanced(pRoot,depth);
    }

    boolean IsBalanced(TreeNode  pRoot,Num pDepth){
        if(pRoot==null){
             pDepth.val=0;
            return true;
        }
        Num leftdepth=new Num(),rightdepth=new Num(); //在递归中声明临时变量，用于求父节点传来的指针对应的值。
 //先判断左右子树满不满足平衡条件，同时记录左右子树的深度
       if(IsBalanced(pRoot.left,leftdepth)&&IsBalanced(pRoot.right,rightdepth)){
//再判断根节点满不满足平衡条件，类似于二叉树遍历的后根遍历
            if(Math.abs(leftdepth.val-rightdepth.val)<=1){
                 pDepth.val=leftdepth.val>rightdepth.val?leftdepth.val+1:rightdepth.val+1;
                return true;
            }
        }
        return false;
    }
}

C++的实现如下：

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        int depth;
        return IsBalanced(pRoot,&depth);
    }

    bool IsBalanced(TreeNode* pRoot,int*pDepth){
        if(pRoot==NULL){
            *pDepth=0;
            return true;
        }

        int leftdepth,rightdepth; //在递归中声明临时变量，用于求父节点传来的指针对应的值。
        if(IsBalanced(pRoot->left,&leftdepth)&&IsBalanced(pRoot->right,&rightdepth)){
            if(abs(leftdepth-rightdepth)<=1){
                *pDepth=leftdepth>rightdepth?leftdepth+1:rightdepth+1;
                return true;
            }
        }
        return false;
    }
};

实现2：

public class Solution {

public boolean IsBalanced_Solution(TreeNode root) {
        return getDepth(root) != -1;
    }

    private int getDepth(TreeNode root) {
        if (root == null) return 0;
        int left = getDepth(root.left);
        if (left == -1) return -1;
        int right = getDepth(root.right);
        if (right == -1) return -1;
        return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);}
}