剑指offer（39）平衡二叉树

/*public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null){
            return true;
        }
        if(Math.abs((getHeight(root.left)) - (getHeight(root.right))) > 1){
            return false;
        }
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    
    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        return Math.max(getHeight(root.left) , getHeight(root.right)) + 1;
    }
}*/
//O(N),按照后序遍历的方法，每个节点最多遍历一次，如果发现不是平衡二叉树立刻退出，还没有遍历的节点也不用再遍历
public class Solution{
    public boolean IsBalanced_Solution(TreeNode root){
        boolean[] res = new boolean[1];
        res[0] = true;
        getHeight(root, 1, res);
        return res[0];
    }
    
    public int getHeight(TreeNode root, int height, boolean[] res){
        if(root == null){
            return height;
        }
        int leftHeight = getHeight(root.left, height + 1, res);
        if(!res[0]){
            return height;
        }
        int rightHeight = getHeight(root.right, height + 1, res);
        if(!res[0]){
            return height;
        }
        if(Math.abs(leftHeight - rightHeight) > 1){
            res[0] = false;
        }
        return Math.max(leftHeight, rightHeight);
    }
}