剑指offer.平衡二叉树

题目：

输入一颗二叉树的节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

思路：

基于对二叉树深度的理解，我们就很简单可以想到如果每个节点的而右子树的深度相差都不超过1，那么按照定义它就是一棵平衡二叉树。但这种思路的时间效率不高。会出现子节点重复遍历的情况。

但如果我们用后序遍历的方法来遍历的话，我们就可以在遍历一个节点之前就可以遍历到它的左右子树。只要在遍历每个节点的时候记录它们的深度，我们就可以判断他们是不是平衡的。

代码实现：

int height(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    if (leftHeight == -1 || rightHeight == -1 || fabs(leftHeight - rightHeight) > 1) {
        return -1;
    } else {
        return fmax(leftHeight, rightHeight) + 1;
    }
}
 
bool isBalanced(struct TreeNode* root) {
    return height(root) >= 0;
}