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

#include <unordered_map>
class Solution {
    unordered_map<TreeNode*, int>hash;
public:
    //思想就是如果当前节点不为空就判断这课数左右高度差是否小于等于1，然后再判断他们子树是否平衡。
  //这里注意一个点是，从上往下会有很多次的重复调用hight函数，造成很多重复计算（父亲算高度会算子树高度，
  //子树算高度又会算一遍），因此采用了记忆话搜索来优化时间复杂度）。
    int hight(TreeNode*root){
        if(hash.count(root))return hash[root];
        if(!root)return 0;
        return hash[root]=max(hight(root->left),hight(root->right))+1;
    }
    bool IsBalanced_Solution(TreeNode* root) {
        // write code here
        if(!root)return true;
        if(abs(hight(root->left)-hight(root->right))>1)return false;
        return IsBalanced_Solution(root->right)&&IsBalanced_Solution(root->left);
    }
};