1. 题目

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。

示例 1：输入：root = [3,9,20,null,null,15,7] 输出：true

示例 2：输入：root = [1,2,2,3,3,null,null,4,4] 输出：false

示例 3：输入：root = [] 输出：true

提示：树中的节点数在范围 [0, 5000] 内 -104 <= Node.val <= 104

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/balanced-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

这题做的太曲折了。一开始定义没整明白，做了很多无用功。后来明确题意了，又因为以前做过的一道题陷入了思维定式，做的非常复杂。

明确题意：

它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树

明确题意就好做了

3. 代码

3.1. 1.0

黑历史，这版代码写的又臭又长

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool help(TreeNode* L,TreeNode* R){
        if(!L&&!R) return true;
        else if(L&&!R){
            if(L->left||L->right) return false;
            else return true;
        }else if(!L&&R){
            if(R->left||R->right) return false;
            else return true;
        }
        else {
            bool flag = help(L->left,L->right) && help(R->left,R->right);
            if(L->left && !L->right) flag = flag && (help(L->left,R->left) || help(L->left,R->right));
            else if(L->right && !L->left) flag = flag && (help(L->right,R->left) || help(L->right,R->right));

            else if(!L->left && !L->right) flag = flag && (help(L->left,R->left) && help(L->left,R->right) );

            else if(L->left && L->right) flag = flag && (help(L->left,R->left) || help(L->left,R->right) || help(L->right,R->left) || help(L->right,R->right));

            if(!R->left && !R->right) flag = flag &&(help(L->left,R->left) && help(L->right,R->left));

            return flag;
        }

    }
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        return help(root->left,root->right);
    }
};

3.2. 2.0

这版递归，重复计算了很多东西。可以改进为提前判断。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxHeight(TreeNode* root){
        if(!root) return 0;
        return max(maxHeight(root->left),maxHeight(root->right))+1;
    }
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        return isBalanced(root->left) && isBalanced(root->right) && 
               abs(maxHeight(root->left)-maxHeight(root->right))<=1;
    }
};

3.3. 3.0

但是，貌似时间性能并没有改善

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int height(TreeNode* root){
        if(!root) return 0;
        int leftHeight = height(root->left);
        if(leftHeight == -1) return -1;
        int rightHeight = height(root->right);
        if(rightHeight == -1) return -1;
        if(abs(leftHeight-rightHeight)>1) return -1;
        return max(leftHeight,rightHeight)+1;
    }
    bool isBalanced(TreeNode* root) {
        return height(root)>=0;
    }
};

110 平衡二叉树