c++ - 此代码有什么问题？它永无止境(二叉树的顶 View )

Question

问题陈述:打印二叉树的顶 View

我的方法:我维护一个队列，队列中有一对，分别用于root->data和horizontal distance(hd)。我将队列中带有hd的根 push 队列，并将其添加到包含map和hd的root->data中。然后我从队列中 pop 。现在，如果有任何 pop 根节点的子节点，我将它们插入队列，上面的过程将继续进行，直到队列不为空。

我的代码:-

void topView(Node * root) {
        queue<pair<int, int>> q;
        map<int, int> m;
        q.push({root->data, 0});
        while(q.empty() == false){
            int node_val = q.front().first;
            int hd = q.front().second;
            m[hd] =node_val;
            q.pop();
            if(root->left){
                int hdl = hd -1;
                q.push({root->left->data, hdl});
            }
            if(root->right){
                int hdr = hd + 1;
                q.push({root->right->data, hdr});

            }


        }
        for(auto i=m.begin();i!=m.end();i++) 
        { 
            cout<<i->second<<" "; 
        } 
    }

**错误:**超过时间限制(即代码不会停止运行)
**注意**:另外，我发现我无法在代码中为每个节点正确更新“水平距离(hd)”。而且我不能将`hd`添加为Node类的成员，因此我必须将其放入此函数本身，而且我也找不到解决方法((hdl`和`hdr`)。
请帮助并对代码进行一些更正。
先感谢您。

Answer 1

您的代码中有两个问题。一种是您只将节点值存储在队列中，而不是节点指针。所以你的遍历条件

if(root->left)

仅检查根节点的子节点。这导致无限循环，因为我们没有遍历根节点。
第二个问题是即使我们正确地遍历了，顶 View 逻辑也没有正确使用 map 。

m[hd] = node_val

由于这将覆盖每个hd，因此将为您提供底 View 。我们想在这里为每个高清镜头第一次出现。我已经更新了代码。

void topView(Node * root) {
        queue<pair<Node*, int>> q;
        map<int, int> m;
        q.push({root->data, 0});
        while(q.empty() == false){
            Node* current_node = q.front().first;
            int node_val = current_node->data;
            int hd = q.front().second;

            if(m.find(hd) == m.end())
                m[hd] =node_val;

            q.pop();
            if(current_node->left){
                int hdl = hd -1;
                q.push({current_node->left, hdl});
            }
            if(current_node->right){
                int hdr = hd + 1;
                q.push({current_node->right, hdr});

            }


        }
        for(auto i=m.begin();i!=m.end();i++) 
        { 
            cout<<i->second<<" "; 
        } 
    }