Sunday, February 24, 2013

tree post order traversal using stack


int GetDiameter2(int& height)
{
if(!root)return 0;
stack<Node*> s;
s.push(root);
Node* prev=NULL;
int res=0;
while(!s.empty())
{
Node* cur=s.top();
if(!prev || prev->L==cur || prev->R==cur)
{
if(cur->L)
s.push(cur->L);
else if(cur->R)
s.push(cur->R);
else
{
s.pop();
cur->tmp=1;
res=max(res,1);

}
}
else if(cur->L==prev)
{
if(cur->R)
s.push(cur->R);
else
{
s.pop();
cur->tmp=cur->L->tmp+1;
res=max(res,cur->L->tmp+1);
}
}
else if(cur->R==prev)
{
s.pop();
if(cur->L)
{
cur->tmp=max(cur->L->tmp,cur->R->tmp)+1;
res=max(res,cur->L->tmp+cur->R->tmp+1);
}
else
{
cur->tmp=cur->R->tmp+1;
res=max(res,cur->R->tmp+1);
}

}
prev=cur;
}
return res;
}

No comments:

Post a Comment