【LeetCode算法】第110题：平衡二叉树

一、题目描述

二、初次解答

三、官方解法

四、总结

一、题目描述

二、初次解答

1. 思路：从上而下访问二叉树的节点，递归判定当前节点的左子树和右子树的高度差是否为0、-1或1，从而判定其是否是平衡二叉树。

2. 代码：
int getHeight(struct TreeNode* root){
    if(!root)
        return 0;
    return fmax(getHeight(root->left), getHeight(root->right))+1;
}

bool isBalanced(struct TreeNode* root) {
    if(!root)
        return true;
    int dif=getHeight(root->right)-getHeight(root->left);
    if(dif>1 || dif<-1)
        return false;
    return isBalanced(root->left) && isBalanced(root->right);
}
3. 优点：容易想到。

4. 缺点：由于自上而下访问会导致getHeight函数被反复执行，时间复杂度为O(n^2)，空间复杂度为O(n)。

三、官方解法

1. 思路：自下而上访问二叉树的节点。设计子函数getHeight来获取左子树和右子树的高度，同时用返回值-1来指定左子树和右子树不是平衡二叉树。只要左子树或右子树不是平衡二叉树，那么整棵树就不是平衡二叉树。

2. 代码：
int getHeight(struct TreeNode* root){
    if(!root)
        return 0;
    int leftHeight=getHeight(root->left);
    int rightHeight=getHeight(root->right);
    if(leftHeight==-1 || rightHeight==-1 || fabs(rightHeight-leftHeight)>1)
        return -1;
    return fmax(leftHeight, rightHeight)+1;
}

bool isBalanced(struct TreeNode* root) {
    return getHeight(root) >= 0;
}
3. 优点：时间复杂度为O(n)。

4. 缺点：空间复杂度为O(n)。