package leetcode.easy;

import jianzhioffer.TreeNode;

/**
 * Created by wangxiaoyi on 15/11/21.
 */
public class BalancedBinaryTree {

    public boolean isBalanced(TreeNode root) {
        boolean ans[] = new boolean[1];
        ans[0] = true;
        //ans[1] = true;
        if(root == null) return true;
        else{
            int left = height(root.left, ans);
            if(ans[0] == false) return false;
            int right = height(root.right, ans);
            if(ans[0] == false) return false;

            if(Math.abs(left - right) > 1) {
                return false;
            }

        }
        return true;
    }

    public int height(TreeNode root, boolean []ans){
        if(ans[0] == false) return -1;//剪枝
        if(root == null) return 0;
        else {
            int left = height(root.left, ans);
            int right = height(root.right, ans);
            if(Math.abs(left - right) > 1) {//在求树高的同时顺便检查是否平衡,不平衡剪枝条
                ans[0] = false;
            }
            return 1 + Math.max(left, right);
        }
    }

}
