解法一

1、思路

• 递归计算每一个二叉树节点的左右子树高度，若所有节点子树的高度差都小于1，则返回true；

• 对节点高度进行了大量重复计算，效率太低，时间复杂度为 $O(NlogN)$。

2、代码

class Solution {
public:
    int getHeight(TreeNode* root)   //计算该节点高度
    {
        if (root == nullptr) return 0;

        //节点高度等于其左右子树中更高的一个高度 + 1
        return max(getHeight(root->left), getHeight(root->right)) + 1;
    }

    bool isBalanced(TreeNode* root) {
        if (root == nullptr) return true;

        int left = getHeight(root->left);
        int right = getHeight(root->right);

        return isBalanced(root->left) && isBalanced(root->right) && abs(left - right) <= 1;
    }
};

解法二

1、思路

• 用一个错误代码-1表示遇到不平衡的节点，只要有一个节点不平衡，就会递归返回错误代码到最上层；

• 不会进行重复计算，时间复杂度为 $O(N)$ ，空间复杂度为 $O(H)$，$H$为二叉树高度。

2、代码

class Solution {
public:
    int checkHeight(TreeNode* root)
    {
        if (root == nullptr) return 0;

        int left = checkHeight(root->left);
        if (left == -1) return -1;

        int right = checkHeight(root->right);
        if (right == -1) return -1;

        if (abs(left - right) > 1)
        {
            return -1;
        }
        else
        {
            return max(left, right) + 1;
        }
    }

    bool isBalanced(TreeNode* root) {
        return checkHeight(root) != -1;
    }
};