110. Balanced Binary Tree

// time: O(N)

bool isBalanced(TreeNode* root) {
    if (root==NULL) return true;
    int left=depth(root->left);
    int right=depth(root->right);
	// 每一个子树都要严格符合要求
    return abs(left-right)<=1 && isBalanced(root->left) && isBalanced(root->right);
}

int depth(TreeNode* root) {
    if (root==NULL) return 0;
    return max(depth(root->left), depth(root->right)) + 1;
}

bool isBalanced(TreeNode* root) {
    int a;
    return ban(root, a);
}

bool ban(TreeNode* root, int& d) {
    if (root == NULL) {
        d = 0;
        return true;
    }
    int left, right;
    if (ban(root->left, left) && ban(root->right, right)) {
        int diff = left-right;
        if (diff >= -1 && diff <= 1) {
            d = 1 + (left > right ? left : right);
            return true;
        }
    }
    return false;
}