题目

二叉树结构如下：

//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

题解

详细题解可参见#110题解

1. 递归法

  • 时间复杂度: $O(n\log n)$
  • 空间复杂度: $O(n)$
class Solution {
public:
    bool isBalanced(TreeNode* root) {//两种方法。1. 递归（速度慢，计算有冗余，写着简单）
        if(!root) return true;//特殊情况
        return abs(maxDepth(root->left)-maxDepth(root->right)) < 2 &&
               isBalanced(root->left) &&
               isBalanced(root->right);
               //若左右子树相差小于2，且递归左子树右子树都是平衡二叉树，则返回真
               //这一部分有大量重复运算，方法2可优化
               //注意第一个条件要用绝对值
    }

    int maxDepth(TreeNode* cur){//直接使用#104的方法
        if(!cur) return 0;
        return max(maxDepth(cur->left),maxDepth(cur->right))+1;
    }
};

2. 递归法(优化)

  • 时间复杂度: $O(n)$
  • 空间复杂度: $O(n)$
class Solution {
public:
    bool isBalanced(TreeNode* root) {//两种方法。2. 递归优化（速度快，计算无冗余）
        if(!root) return true;//特殊情况
        if(maxDepth(root) == -1) return false;//若为-1说明不为平衡二叉树
        else return true;
    }

    int maxDepth(TreeNode* cur){
        //#104方法的改进,除了检测最大深度还通过直接判断左右子树是否为平衡二叉树来判断主树。
        if(!cur) return 0;//节点为空，直接返回0
        int left = maxDepth(cur->left);
        if(left == -1) return -1;//递归左子树获得左子树最大深度并直接进行判断
        int right = maxDepth(cur->right);
        if(right == -1) return -1;//右子树同上
        int diff = abs(right-left);//计算高度差
        if(diff > 1) return -1;//深度差>1,返回结果
        else return max(left,right)+1;//否则返回最大深度
    }
};