This is for finding the top view of a binary tree. My logic has been line by line traversal of the tree. I have used two maps here, m2 for storing node and horizontal distance, the other(m1) with horizontal distance and node data. It seems to fail for a specific case(I cannot copy the test case here because the test case is too large and is not shown completely) in GFG : Link to question
void topView(struct Node *root)
{
if(root==NULL)
return;
queue<Node *> q;
map<Node *,int> m2;
map<int,int> m1;
m1[0]=root->data;
m2[root]=0;
q.push(root);
while(!q.empty())
{
if(q.front()->left)
{
q.push(root->left);
if(m1.find(m2[root]-1)==m1.end())
{
m2[root->left]=m2[root]-1;
m1[m2[root]-1]=root->left->data;
}
}
if(q.front()->right)
{
q.push(root->right);
if(m1.find(m2[root]+1)==m1.end())
{
m2[root->right]=m2[root]+1;
m1[m2[root]+1]=root->right->data;
}
}
q.pop();
root=q.front();
}
for(auto i:m1)
cout<<i.second<<" ";
}
Aucun commentaire:
Enregistrer un commentaire