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

判断是不是平衡二叉树：最直观的想法是，首先使用umap存储二叉树结点以及其对应的高度，然后编写一个函数dfs来后序遍历并记忆化搜索存储二叉树各个节点的高度。如果使用递归的思路来考虑该题，则直接考虑平衡二叉树的条件即为左右子树高度差的绝对值不超过1且左右子树均平衡。注意，将判断平衡的部分单独抽离出来并封装成一个函数，否则其会多次调用主函数中的dfs()部分。

抽离前：

// umap统计 节点 节点高度
    unordered_map<TreeNode *,int> umap;
    // 求高度 后序遍历
    int dfs(TreeNode* cur)
    {
        // 空节点高度为0
        if(!cur)
            return 0;
        // 记忆化搜索
        if(umap.find(cur)!=umap.end())
            return umap[cur];
        // 左
        int left = dfs(cur->left);
        int right = dfs(cur->right);
        // 根节点高度等于左右子树最大高度加一
        return umap[cur]=max(left,right)+1;
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        // 默认空树平衡
        if(!pRoot)
            return true;
        dfs(pRoot);
        // 平衡二叉树的要求是左子树平衡且右子树平衡且左右子树高度差小于等于1
        return abs(umap[pRoot->left]-umap[pRoot->right])<=1 && IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
    }

抽离后：

// umap统计 节点 节点高度
    map<TreeNode *,int> umap;
    // 求高度 后序遍历
    int dfs(TreeNode* cur)
    {
        // 空节点高度为0
        if(!cur)
            return 0;
        // 记忆化搜索
        if(umap.find(cur)!=umap.end())
            return umap[cur];
        // 左
        int l = dfs(cur->left);
        int r = dfs(cur->right);
        // 根节点高度等于左右子树最大高度加一
        return umap[cur]=max(l,r)+1;
    }
    bool isBalance(TreeNode* root)
    {
        if(!root)
            return true;
         // 平衡二叉树的要求是左子树平衡且右子树平衡且左右子树高度差小于等于1
        return abs(umap[root->left]-umap[root->right])<=1 && isBalance(root->left) && isBalance(root->right);
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        // 默认空树平衡
        if(!pRoot)
            return true;
        dfs(pRoot);
        return isBalance(pRoot);
    }

优化：上述方法我们是先求出高度再判断是否平衡，其实我们可以边求高度边判断平衡。后序遍历求高度，先求左子树高度，再求右子树高度，接着求左右子树高度差绝对值，如果其大于1则表明不平衡则返回-1，反之返回该节点的高度值，同时在左右子树高度返回时也要判断是否为-1，并及时返回-1。

// 求高度 后序遍历
int dfs(TreeNode* cur)
{
   // 空节点高度为0
   if(!cur)
     return 0;
   // 左子树高度
   int left = dfs(cur->left);
   // 左子树平衡则返回高度 反之返回不平衡
   if(left==-1)
      return -1;
   // 右子树高度
   int right = dfs(cur->right);
   // 右子树平衡则返回高度 反之返回不平衡
   if(right==-1)
     return -1;
   // 左右子树高度差
   int diff = abs(left-right);
   // 高度差大于1不平衡
   if(diff>1)
      return -1;
   // 树的高度
   return max(left,right)+1;
}
bool IsBalanced_Solution(TreeNode* pRoot) 
{
    // 默认空树平衡
    if(!pRoot)
        return true;
    return dfs(pRoot)==-1?false:true;
}