题意理解

判断一棵树是否为平衡二叉树。
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

方法一

使用一个map来记录每个结点的高度height，每个结点的高度等于max(height左，height右)+1。
示意图如下：

然后对二叉树进行先序遍历，比较每个结点的左子树和右子树的高度就可以判断该点是否满足平衡条件，再向左子树和右子树递归。

具体代码如下：

class Solution {
public:
    map<TreeNode*, int> height;
    //计算每个结点的高度height
    int depth(TreeNode *p) {
        if (!p) return 0;
        height[p] = max(depth(p->left),depth(p->right)) + 1;
        return height[p];
    }
    //先序遍历，从根到叶子看每个结点是否满足平衡条件
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if (pRoot == nullptr) return true;
        depth(pRoot);
        if (abs(height[pRoot->left]-height[pRoot->right])>1) return false;
        return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
    }
};

时间复杂度：。求height和判断是否平衡的时候各遍历了一遍二叉树，消耗的时间均为。
空间复杂度：。创建了一个map来记录二叉树的高度，消耗了的空间；同时递归调用深度也为。

方法二

在方法一中，求height的过程是从下而上的，那我们可以在求height的时候顺便判断其左右孩子是否平衡，并且确定该结点是否平衡。如果不平衡，则将该结点的高度记为-1，并停止其余的计算和比较过程。

具体代码如下：

class Solution {
public:
    //先求两个子树的高度，进行比较后，再返回该结点的高度。
    int depth(TreeNode *p) {
        int l,r;
        if (!p) return 0;
        l = depth(p->left);
        if (l == -1) return -1;//如果左子树不平衡，则该结点不用再比较了。
        r = depth(p->right);
        if (r == -1) return -1;//如果右子树不平衡，则该结点不用再比较了。
        if (abs(l - r)>=2) return -1;
        return max(l,r) + 1;
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if (depth(pRoot) == -1) return false;
        return true;
    }
};

时间复杂度：。求height和判断二叉树是否平衡同时进行，消耗的时间为。
空间复杂度：。没有开辟额外空间，消耗空间为递归的深度。