本文共 861 字，大约阅读时间需要 2 分钟。

不多说，首先给出我的常规解法：递归访问整棵树，计算子树的高度

int depth(TreeNode* root)    {        if(root==NULL) return 0;        return max(depth(root->left),depth(root->right))+1;    }    bool isBalanced(TreeNode *root) {        if(root==NULL)            return true;        if(isBalanced(root->left)&&isBalanced(root->right))        {            return abs(depth(root->left)-depth(root->right))>1?false:true;        }        return false;    }

很明显：节点高度会被重复计算，效率不高，时间复杂度为O(nlgn);

改进算法如下：

int depth(TreeNode* root)    {        if(root==NULL) return 0;        int leftlen=depth(root->left);        int rightlen=depth(root->right);        if(leftlen==-1||rightlen==-1)            return -1;        return abs(leftlen-rightlen)>1?-1:max(leftlen,rightlen)+1;    }    bool isBalanced(TreeNode *root) {        if(root==NULL)            return true;        return depth(root)==-1?false:true;    }

转载地址：https://blog.csdn.net/weixin_40599276/article/details/100078159 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！