lundi 25 mai 2020

Failing for specific case

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