Несоблюдение указания c случай - PullRequest
Новая
       105

Несоблюдение указания c случай

0 голосов
/ 26 мая 2020

Это для поиска вида сверху двоичного дерева. Мой лог c был построчным обходом дерева. Я использовал здесь две карты: m2 для хранения узла и горизонтального расстояния , другую ( m1 ) с горизонтальным расстоянием и данными узла . Кажется, что это не удается для конкретного случая c (я не могу скопировать тестовый пример здесь, потому что тестовый пример слишком велик и не показан полностью) в GFG: Ссылка на вопрос Вот частичный тестовый пример Я могу получить: 

1
338
5 4 L 5 4 R 4 8 L 4 -1 N 4 2 L 4 2 R 8 8 L 8 -1 N 2 4 L 2 7 R 2 5 L 2 -1 N 8 9 L 8 3 R 4 9 L 4 -1 N 7 5 L 7 3 R 5 8 L 5 -1 N 9 1 L 9 8 R 3 1 L 3 -1 N 9 10 L 9 10 R 5 5 L 5 -1 N 3 7 L 3 6 R 8 9 L 8 -1 N 1 3 L 1 10 R 8 6 L 8 -1 N 1 7 L 1 10 R 10 4 L 10 -1 N 10 7 L 10 10 R 5 8 L 5 -1 N 7 1 L 7 9 R 6 10 L 6 -1 N 9 3 L 9 10 R 3 10 L 3 -1 N 10 2 L 10 4 R 6 2 L 6 -1 N 7 7 L 7 7 R 10 3 L 10 -1 N 4 5 L 4 3 R 7 1 L 7 -1 N 10 3 L 10 2 R 8 10 L 8 -1 N 1 2 L 1 1 R 9 10 L 9 -1 N 10 1 L 10 4 R 3 8 L 3 -1 N 10 8 L 10 7 R 10 9 L 10 -1 N 2 4 L 2 7 R 4 2 L 4 -1 N 2 6 L 2 1 R 7 10 L 7 -1 N 7 6 L 7 10 R 3 3 L 3 -1 N 5 8 L 5 5 R 3 9 L 3 -1 N 1 9 L 1 4 R 3 6 L 3 -1 N 2 3 L 2 3 R 10 7 L 10 -1 N 2 4 L 2 7 R 1 7 L 1 -1 N 10 6 L 10 6 R 1 8 L 1 -1 N 4 6 L 4 8 R 8 7 L 8 -1 N 8 9 L 8 1 R 7 4 L 7 -1 N 9 10 L 9 2 R 4 6 L 4 -1 N 7 1 L 7 1 R 2 9 L 2 -1 N 6 4 L 6 2 R 1 6 L 1 -1 N 10 9 L 10 4 R 6 9 L 6 -1 N 10 2 L 10 6 R 3 1 L 3 -1 N 8 2 L 8 8 R 5 1 L 5 -1 N 9 3 L 9 6 R 9 7 L 9 -1 N 4 3 L 4 2 R 6 2 L 6 -1 N 3 10 L 3 .................

Ожидаемый результат: 

5 3 10 9 10 3 1 9 8 8 4 5 4 2 6 8 3

Мой результат: 

5 3 10 9 10 3 1 9 8 8 4 5 4 2

Мой код: 

// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;

struct Node
{
    int data;
    struct Node *left;
    struct Node *right;

    Node(int x){
        data = x;
        left = NULL;
        right = NULL;
    }
};

void topView(struct Node *root);


int main()
{
    int t;cin>>t;
    while(t--)
    {
        int n,i,k;
        cin>>n;
        i=n;

        Node* root=NULL;
        queue <Node*> q;
        while(i>0)
        {
            int a,b;
            char c;
            cin>> a >> b >> c;
            if(!root){
                root = new Node(a);
                q.push(root);
            }
            Node* pick = q.front();
            q.pop();

            if(c == 'L'){
                pick->left = new Node(b);
                q.push( pick->left );
            }
            cin>> a >> b >> c;
            if(c == 'R'){
                pick->right = new Node(b);
                q.push( pick->right );
            }
            i-=2;
        }
//        inorder(root);
//        cout<<endl;
        topView(root);
        cout << endl;
    }
    return 0;
}




// } Driver Code Ends


//Structure of binary tree
/*struct Node
struct Node
{
    int data;
    struct Node* left;
    struct Node* right;

    Node(int x){
        data = x;
        left = right = NULL;
    }
};*/
// function should print the topView of the binary tree
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<<" ";
}

1 Ответ

0 голосов
/ 26 мая 2020

Проблема в том, что вы добавляете новые члены в m2, когда root виден сверху дерева: 

    if(m1.find(m2[root]+1)==m1.end())
    {
        m2[root->right]=m2[root]+1;

Это не будет работать для такого тестового примера 

    1
    10
    1 2 L 1 5 R 2 -1 N 2 3 R 5 -1 N 5 -1 N 3 -1 N 3 4 R 4 -1 N 4 6 R

, который имеет следующее дерево: 

            1
           / \
          2   5
           \
            3
             \
              4
               \
                6

Ожидаемый результат будет 

    2 1 5 6

, но ваш код приведет к 

    2 1 5

Здесь, когда root является узлом 2, узел 3 будет добавлен к m2. Но когда узел 3 root, он не добавит узел 4 к m2, поскольку узел 3 не может быть виден сверху и, следовательно, не инициализирует его правильно в положение 1.

Впоследствии, когда root установлен на узел 4, он будет искать его в m2. Но поскольку этот ключ еще не существует, он создаст новое значение с помощью стандартного конструктора int (0). Из-за этого ваш код предполагает, что узел 6 находится в позиции 1, которая уже затмевается узлом 5.

Однако исправить это просто. Просто переместите присвоения m2 из if-clauses: 

m2[root->left]=m2[root]-1;
if(m1.find(m2[root]-1)==m1.end())
{
    m1[m2[root]-1]=root->left->data;
}

То же самое для правого случая.

...