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

• ``````#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;
}``````

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