navneetsingh5189
BAN USERI have a O(dn) solution where d is the depth of the tree and n is the length of the string.
int find_depth(string str) {
int count = -1;
bool found;
if (str.length() < 4)
return -1;
while (str != "0") {
cout << str << endl;
found = false;
int len = str.length();
int i = 0;
while (i<len){
if (str[i] == ')') {
if (i >= 3 && str.substr(i-3,4)=="(00)") {
string temp = str.substr(0, i - 3) + "0" + str.substr(i + 1, len - i - 1);
len = len - 3;
str = temp;
found = true;
}
else
return -1;
}
i++;
}
if (found == false)
return -1;
else
count++;
}
return count;
}
Here are two solutions.
1) Using Parent pointer and HashTable.
If the tree is balanced:
Time:O(log n)
Space:O(log n)
else both time and space are of the order of O(n)
Node* commonAncestorWithParent(Node* p,Node* q){
unordered_map<Node*,Node*> HashTable;
while(p!=NULL){
HashTable.insert(make_pair(p,p));
p=p->pParent;
}
while(q!=NULL){
if(HashTable.find(q)!=HashTable.end())
return HashTable.find(q)->second;
q=q->pParent;
}
return NULL;
}
2) Solution without parent pointer and no other data structure. I think it's quite optimal.
Time: O(n)
Space: O(1)
Node* commonAncestorWithoutParent(Node*root,Node*p,Node*q){
Node *left=NULL,*right=NULL;
if(root==p||root==q)
return root;
if(root->pLeft!=NULL)
left=commonAncestorWithoutParent(root->pLeft,p,q);
if(root->pRight!=NULL)
right=commonAncestorWithoutParent(root->pRight,p,q);
if(left!=NULL){
if(right!=NULL)
return root;
return left;
}
else{
if(right!=NULL)
return right;
return NULL;
}
}
Here are two solutions.
1) Using Parent pointer and HashTable.
If the tree is balanced:
Time:O(log n)
Space:O(log n)
else both time and space are of the order of O(n)
Node* commonAncestorWithParent(Node* p,Node* q){
unordered_map<Node*,Node*> HashTable;
while(p!=NULL){
HashTable.insert(make_pair(p,p));
p=p->pParent;
}
while(q!=NULL){
if(HashTable.find(q)!=HashTable.end())
return HashTable.find(q)->second;
q=q->pParent;
}
return NULL;
}
2) Solution without parent pointer and no other data structure. I think it's quite optimal.
Time: O(n)
Space: O(1)
Node* commonAncestorWithoutParent(Node*root,Node*p,Node*q){
Node *left=NULL,*right=NULL;
if(root==p||root==q)
return root;
if(root->pLeft!=NULL)
left=commonAncestorWithoutParent(root->pLeft,p,q);
if(root->pRight!=NULL)
right=commonAncestorWithoutParent(root->pRight,p,q);
if(left!=NULL){
if(right!=NULL)
return root;
return left;
}
else{
if(right!=NULL)
return right;
return NULL;
}
}
A Simple Solution which runs in O(n) and O(n) extra space (Stack space)
- navneetsingh5189 November 20, 2014