这段代码有什么问题？它永远不会结束（二叉树的顶视图）

Question

问题陈述：打印二叉树的顶视图

我的方法：我维护一个队列，其中每个队列都有一对 root->data 和 horizontal distance(hd)。我将带有 hd 的根推送到队列中，并将其添加到包含 hd 和 root->data 的 map。然后我从队列中弹出。现在，如果有 children 个弹出的根，我将它们插入队列，并且上述过程一直发生，直到队列不为空。

我的代码：-

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` 添加为 Node class 的成员，因此我必须将其放入此函数本身，但我无法找到实现它的方法。（`hdl` 和 ` hdr`)
请帮助并对代码进行一些更正。
先感谢您。

Answer 1

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

if(root->left)

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

m[hd] = node_val

因为这是对每个高清的覆盖，所以这会给你底视图。我们想要这里每个高清的第一次出现。我更新了代码。

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

这段代码有什么问题？它永远不会结束（二叉树的顶视图）

What is the problem with this code? It never ends (Top View of a Binary Tree)

c++

error-handling

tree

binary-tree