题解 | #判断是不是平衡二叉树#

递归思路：

• 空树一定为平衡二叉树
• 一棵树是平衡二叉树，首先需要它的左右子树都是平衡二叉树，这点可以用返回值bool来递归解决
• 一棵树是平衡二叉树，其次需要它自己左右子树的高度差不超过1，这点不能用bool来解决，所以考虑将返回值改成pair<bool, int>，bool存储是否为平衡二叉树，而int存储该二叉树的高度。
• 按照上面两个条件由左右子树的返回值计算该树的返回值。

class Solution {
public:
    pair<bool, int> IsBalanced_Solution2(TreeNode* pRoot) {
        if (!pRoot) return make_pair(true, 0);
        auto l = IsBalanced_Solution2(pRoot->left), r = IsBalanced_Solution2(pRoot->right);
        return make_pair(l.first && r.first && abs(l.second - r.second) <= 1, max(l.second, r.second) + 1);
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        return IsBalanced_Solution2(pRoot).first;
    }
};