Sharing of my 80 ms AC solution in O(log(n)*log(n)) time


  • 0
    R
    #include <stdlib.h>
    #include <iostream>
    using namespace std;
    
     struct TreeNode 
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
         TreeNode() : val(-1), left(NULL), right(NULL) {}
     };
    class Solution {
    public:
        int getHeight(TreeNode* root)
        {
            if(root==NULL)
                return 0;
            else
                return 1+getHeight(root->left);
        }
        bool isInTree(TreeNode* root,int index,int h)
        {
            int pos=h-1;
            TreeNode* cur=root;
            while(pos>=0)
            {
                if(index & (1<<(pos--)))
                    cur=cur->right;
                else
                    cur=cur->left;
                if(cur==NULL)
                    return false;
            }
            return true;
        }
        int countNodes(TreeNode* root)
        {
            int h=getHeight(root)-1;
            if(h==-1)
                return 0;
            int s=0;
            int e=(1<<h)-1;
            int m;
            while(e-s>1) {
                m=(s+e)/2;
                if(isInTree(root,m,h))
                    s=m;
                else
                    e=m;
            }
            if(isInTree(root,e,h))
                s=e;
            if(h>0)
                return s+(1<<h);
            else
                return s+1;
        }
        int countNodes_recursive(TreeNode* root) {
            if(NULL==root)
                return 0;
            else
                return 1+countNodes_recursive(root->left)+countNodes_recursive(root->right);
        }
    };
    void test(int arr[],int expect)
    {
        static int cnt=0;
        Solution s;
        TreeNode* tree=new TreeNode[expect];
        for(int i=0;i<expect;i++)
        {
            tree[i].val=i+1;
            if(2*i+1<expect)
                tree[i].left=&(tree[2*i+1]);
            if(2*i+2<expect)
                tree[i].right=&(tree[2*i+2]);
        }
        //int result=s.countNodes_recursive(&(tree[0]));
        int result=s.countNodes_recursive(&(tree[0]));
        if(result==expect)
            cout<<"case#"<<cnt++<<" Passed."<<endl;
        else
            cout<<"case#"<<cnt++<<" WA. "<<result<<endl;
        delete tree;
    
    }
    int main()
    {
    
        int N=50000;
        int* arr=new int[N];
        for(int i=0;i<N;i++) { 
            arr[i]=i+1;
            test(arr,i+1);
        }
        delete arr;
        return 0;
    }

Log in to reply
 

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