Share my O(h^2) (O(lgnlgn)) solution


  • 0
    R
    class Solution {
    public:
        int countNodes(TreeNode* root) {
            if(!root) return 0;
            TreeNode* p=root;
            int lcnt=0;
            while(p){
                p=p->left;
                lcnt++;
            }
            TreeNode* q=root;
            int rcnt=0;
            while(q){
                q=q->left;
                rcnt++;
            }
            if(lcnt==rcnt) return (1<<lcnt)-1;
            p=root->left;
            int lrcnt=1;
            while(p){
                p=p->right;
                lrcnt++;
            }
            if(lrcnt==lcnt){
                return (1<<(lcnt-1))+countNodes(root->right);
            }else{
                return countNodes(root->left)+(1<<(rcnt-1));
            }
        }
    };
    

    maybe is a little long, but very clear logic, I just use divide and conque, I find that it must can be divided into a complete tree and a full tree(left or right substree is full tree), and it depends on whether the right most node of left substree is in the last level or not, so three O(h) traverse and divide and conquer


  • 0

    That's obviously not O(h) but only O(h2), just like everybody else's.


  • 0
    R

    T(n)=T(n/2)+O(lgn), really? but I don't know how to use master theory to get T(n)
    but if h=O(lgn) h^2=O(lgn^2)=O(lgn) right?


  • 0

    You mean master theorem? It's actually pretty simple, and I can recommend the Wikipedia page about it. But you really don't need it to know that h+(h-1)+(h-2)+...+3+2+1 is proportional to h^2.

    No, O((lgn)^2) isn't O(lgn). Are you thinking about O(lg(n^2)) instead? That's O(lgn), but it's not what you have here.


  • 0
    R

    Sure, you are right. Can be O(h^2) that is O(lgnlgn) not O(lgn)


  • 0

    Hmm, your title still says O(h). Did you forget to fix it or are you still not fully convinced?


  • 0
    R

    Thanks for your remind : )


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.