时间戳

首页 > 解决方案 > 这段代码有什么问题？它永远不会结束（二叉树的顶视图）

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

问题描述

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

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

我的代码：-

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`）
请帮助并对代码进行一些更正。
先感谢您。

标签： c++error-handlingtreebinary-tree

解决方案

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

if(root->left)

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

m[hd] = node_val

由于这是覆盖每个高清，这将为您提供底部视图。我们希望这里的每个 hd 第一次出现。我已经更新了代码。

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

推荐阅读