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

class Solution {
public:
    int IsBalanced_Solution2(TreeNode *root) {
        if (!root) return 0;
        auto l = IsBalanced_Solution2(root->left);
        auto r = IsBalanced_Solution2(root->right);
        if (l == -1 || r == -1 || abs(r - l) > 1) {
            return -1;
        }
        return max(l, r) + 1;
    }

    bool IsBalanced_Solution(TreeNode* pRoot) {
        return IsBalanced_Solution2(pRoot) != -1;
    }
};

思路：递归

* 判断是否平衡需要二叉树高度，所以递归函数必须返回高度。

* 高度必须大于等于0，所以可以用-1来表示子树不平衡。

* 当前节点为根的二叉树平衡的条件：

** 左右子树平衡。

** 左右子树高度差不超过1。