特定情况下失败

Question

这是为了找到二叉树的顶视图。我的逻辑是逐行遍历树。我这里用了两张图，m2用于存储节点和水平距离，另一个（m1）具有水平距离和节点数据。它似乎在 GFG 中针对特定用例失败（我无法在此处复制测试用例，因为测试用例太大并且未完全显示）：Link to question 这是我可以获得的部分测试用例：

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<<" ";
}

Answer 1

问题是当从树的顶部看到 root 时，您将新成员添加到 m2：

    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

它有以下树：

预期输出为

    2 1 5 6

但是您的代码会导致

    2 1 5

这里，当root为节点2时，节点3将添加到m2。但是当 root 节点 3 时，它不会将节点 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;
}

右例也一样。

特定情况下失败

Failing for specific case

c++

tree

binary-tree

c++11

c++14