二叉树顶视图的歧义

Question

二叉树的顶视图到底是什么？

我发现我找到的文章中存在很大的歧义和不明确。

例如geeksforgeeks上面展示的俯视图：

       1
    /     \
   2       3
  /  \    / \
 4    5  6   7

他们继续说顶视图是 4 2 1 3 7。这里的问题是他们对什么不是顶视图留下了很多猜测。因此，在代码中实现变得模棱两可。

examples so far are not any better. Hackerrank的例子更糟。

所以我希望有人能明确告诉我顶视图是什么，因为我已经尝试了 2 天。例如，这棵树的顶视图是什么：

如果我可以大胆地问，为什么它很重要？

Answer 1

我不知道您有什么技术或数学定义，但从链接中可以看出树的顶视图如下：

想象一下你的树躺在 table 的表面上。从 table 的根端向下看。假设节点的值写在小木块上，它们之间的联系用木块表示，木块高到足以遮住它们后面的任何节点，当你低头到table高度时，你能看到哪些节点？在第一个示例中，5 和 6 是模糊的，而 2、3、4 和 7 向左或向右向外延伸，因此它们仍然可见。

但是，正如您的第二个示例所示，关于节点 2、5、11、12、13 是否向外延伸到足以可见的程度，这是不明确的。

这似乎是一个定义不清的概念，这可能意味着它不值得担心。

Answer 2

现在要了解顶视图的定义，最好的方法就是知道如何找到一棵树的顶视图。

求顶视图是两种遍历的组合->水平顺序遍历和垂直遍历（还有其他方法，但这是最基本的）。

为了形象化，开始在树中绘制垂直线，在第二个示例中，将绘制 6 条垂直线覆盖节点，1st -> 2,5 ||第二 -> 1,3,4 ||第三 -> 14,7,6,8 ||第四 -> 15,13,10,9 ||第 5 -> 11 ||第 6 -> 12。现在遍历这些垂直线的前导，这将给出树的顶视图 2->1->14->15->11->12.

这就像你一直盯着树的顶部开始画直线，直线在接触任何其他节点之前首先切割的节点是树的顶视图。

像 hackerrank 上的所有其他问题一样有助于加强您的基本概念，找到顶视图可以帮助您详细了解水平顺序遍历和垂直遍历概念。

Answer 3

为了回答你的问题，我会要求你假设一个粗略的草图，以实际理解俯视图所要求的问题。您可能会假设您正在观看这棵树，其中 二叉树的根部 作为从上方的直升飞机上的 树的峰值 。

假设根的秩为0。您需要按级别顺序遍历树。如果您向 左转，则当前等级降低 1，而当您向 右转时，当前等级增加 1。然后您将能够看到 只有每个排名 的唯一值 作为输出。排名实际上是root node的horizontal distance。

就像第一个例子：

             ------- 1 (0) -------
            /                     \
        2 (0-1=-1)               3 (0+1=1)
      /           \             /          \
   4 (-1-1=-2)  5 (-1+1=0)    6 (1-1=0)   7 (1+1=2)

我在括号中写下了我所指的 ranks。因此，如果要求按照 GeeksForGeeks 中的要求从 从左到右 书写，则最终输出，您可以打印根据等级排序的每个唯一等级的相应数字。

而且我想现在很清楚为什么 5 (rank=0) 和 6(rank=0) 不在最终答案中。因为当从树的顶部看时，这些数字将被 1(rank=0) 遮蔽。

map<int,int> mp;

void topView(Node * root) {
    if(!root)
        return;

    mp.insert({0,root->data});

    queue<pair<Node*,int>> q;
    q.push({root,0});
    while(!q.empty()){
        Node *tmp=q.front().first;
        int dis=q.front().second;
        q.pop();

        if(tmp->left){
            q.push({tmp->left,dis-1});

            if(mp.find(dis-1)==mp.end()){
                mp.insert({dis-1,tmp->left->data});
            }
        }

        if(tmp->right){
            q.push({tmp->right,dis+1});

            if(mp.find(dis+1)==mp.end()){
                mp.insert({dis+1,tmp->right->data});
            }
        }
    }

    for(auto i : mp){
        cout<<i.second<<" ";
    }

}

上述问题的公认解决方案。 Link : 解释得很好！请参阅逐步说明。

二叉树顶视图的歧义

Ambiguity with the Top View of a binary tree

binary-tree

data-structures