一、题目描述

题目大意：输入一棵二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
注：我们约定空树是平衡二叉树
注意审题：空树是平衡二叉树

算法（自底向上递归）

算法思路

1.总体思路：判断一棵树是不是平衡二叉树,也就是判断它左子树和右子树的高度差是否超过了1,因此我们可以自底向上上递归,每次检查以当前结点为根的数是否满足条件,然后将判断条件上传
2.我们每次都要调用一个求二叉树高度的函数,因此时间复杂度较高

代码实现（C++11）

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        return check(pRoot);
    }

    bool check(TreeNode* root){
        if(!root) return true;
        int left = dfs(root->left);
        int right = dfs(root->right);
        if(abs(left - right) > 1) return false;
        return check(root->left) && check(root->right);
    }

    int dfs(TreeNode* root){
        if(!root) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        return max(left, right) + 1;
    }
};

时间复杂度：O(n^2)
空间复杂度：O(n^2)

时间复杂度优化

其实我们可以用-1来代替不合法的状态,若某棵子树的高度为-1,则代表整棵树都不是平衡二叉树,因此我们可以自底向上递归来求每棵树的高度,比较它两颗子树的高度差是否满足条件,满足则返回合法的高度,否则返回-1

代码实现（C++11）

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        return dfs(pRoot) != -1;
    }

    int dfs(TreeNode* root){
        if(!root) return 0;
        int left = dfs(root->left);
        if(left == -1) return -1;
        int right = dfs(root->right);
        if(right == -1) return -1;
        return abs(left - right) > 1 ? -1 : max(left, right) + 1;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)