Tuesday, March 5, 2013

rebuild BST


Node* RebuildBST(vector<int> output)
{
int n=output.size();
if(n==0)
return NULL;
stack<Node*> myStack;
int i=0;
Node* root;
while(i<n)
{
int curVal=output[i];
Node* preNode=NULL,*prePreNode=NULL;
while(!myStack.empty())
{
preNode=myStack.top();
if(preNode->val>curVal)
break;
prePreNode=myStack.top();
myStack.pop();
}
Node* curNode=new Node;
curNode->val=output[i];
curNode->L=NULL;
curNode->R=NULL;
if(!preNode)
{
root=curNode;
}
else if(!prePreNode)
{
preNode->L=curNode;
}
else
{
prePreNode->R=curNode;
}
myStack.push(curNode);
i++;
}
return root;
}

No comments:

Post a Comment