LeetCode 110. Balanced Binary Tree

发布时间：2020-12-14 03:48:33 所属栏目：大数据来源：网络整理

导读：二叉树的问题，这里主要关心一下时间复杂度。先回忆一下求二叉树深度的问题，T(n) = 2T(n/2)+1 - O(n) 本题 T(n) = 2T(n/2) + O(n) - O(nlogn)? 最坏情况是O(n^2) class Solution { public : bool isBalanced(TreeNode* root) { if (root==NULL) return tru

二叉树的问题，这里主要关心一下时间复杂度。

先回忆一下求二叉树深度的问题，T(n) = 2T(n/2)+1 -> O(n)

本题 T(n) = 2T(n/2) + O(n) -> O(nlogn)? 最坏情况是O(n^2)

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

可以继续优化，一旦发现子树不是平衡的，返回-1，最后只要判断 f(root)!=-1 就可以了

时间复杂度O(n)，空间复杂度O(H)

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return depth(root)!=-1;
    }
    
    int depth(TreeNode *root){
        if (root==NULL) return 0;
        int left=depth(root->left);
        if (left==-1) return -1;
        int right=depth(root->right);
        if (right==-1) return -1;
        if (abs(left-right)>1) return -1;
        return 1+max(left,right);
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!