题意

输入一棵节点数为 n 的二叉树，判断该二叉树是否是平衡二叉树。

思路

平衡二叉树是满足以下两种条件的二叉树：左右子树高度差相差小于等于1且左右子树都为平衡二叉树。 于是我们可以使用递归和深搜来判断一棵树受否为平衡二叉树，先判断高度是否满足条件，再递归判断左右子树是否为平衡二叉树。

class Solution {
public:
    int dfs(TreeNode* now)
    {
        if(now == NULL) return 0;//若当前节点不存在，返回高度为0
        if(now->left == NULL && now->right == NULL) return 1;
        return max(dfs(now->right),dfs(now->left))+1;//否则继续搜索左右子树
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(pRoot == NULL) return true;//空树为平衡二叉树
        if(pRoot->left == NULL && pRoot->right == NULL) return true;//左右子树若
        if(abs(dfs(pRoot->left)-dfs(pRoot->right))>1) return false;//若左右子树相差大于1不为平衡二叉树
        return IsBalanced_Solution(pRoot->right) && IsBalanced_Solution(pRoot->left);//递归判断左右子树
    }
};

复杂度分析

时间复杂度：$O(n^2)O(n^2)$，越靠近根节点所搜索时间越长。

空间复杂度：$O(n^2)O(n^2)$，为dfs所消耗栈空间。

改进

我们可以观察到，同一棵树是否为平衡二叉树在搜索中保持不变，所以我们可以利用记忆化搜索的方法减少复杂度。

class Solution {
public:
    void init(TreeNode* now)
    {
        if(now == NULL) return;
        now->val=0;
        init(now->left);
        init(now->right);
    }
    int dfs(TreeNode* now)
    {
        if(now == NULL) return 0;//若当前节点不存在，返回高度为0
        if(now->val) return now->val;//已经计算过了直接输出
        if(now->left == NULL && now->right == NULL) return 1;
        return now->val=max(dfs(now->right),dfs(now->left))+1;//否则继续搜索左右子树，并将结果保存
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        init(pRoot);//初始化树高存储
        if(pRoot == NULL) return true;//空树为平衡二叉树
        if(pRoot->left == NULL && pRoot->right == NULL) return true;//左右子树若
        if(abs(dfs(pRoot->left)-dfs(pRoot->right))>1) return false;//若左右子树相差大于1不为平衡二叉树
        return IsBalanced_Solution(pRoot->right) && IsBalanced_Solution(pRoot->left);//递归判断左右子树
    }
};

复杂度分析

时间复杂度：$O(n)O(n)$,每棵树只需搜索一次。

空间复杂度：$O(n)O(n)$，为dfs所消耗栈空间。