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

class Solution {
  public:

    int high(TreeNode* p) {
        if (!p)
            return 0;
        return max(high(p->left), high(p->right)) + 1;

    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if (!pRoot)
            return 1;
        if (abs(high(pRoot->right) - high(pRoot->left)) > 1)
            return 0;
        if (!IsBalanced_Solution(pRoot->left))
            return 0;
        if (!IsBalanced_Solution(pRoot->right))
            return 0;

        return 1;
    }
};

先写一个求高度的函数

若是有难点，难点在于递归的理解

这是一个自顶向下的方法

1.为空树：符合

2.本级任务：本树平衡，则符合，否则交给下级任务

3.左子树不平衡：不符合

4.右子树不平衡：不符合