二叉树的顶视图存在歧义

Question

二叉树的顶视图究竟是什么？

我发现现有的文章都存在很大的模糊性和缺乏清晰度。

例如，以下内容是用于展示顶视图的 geeksforgeeks 的示例：

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

他们接着说，顶部视图是4 2 1 3 7。问题在于他们留下了很多关于不是顶部视图的猜测。因此，在代码实现上变得模棱两可。

Stackoverflow 的示例到目前为止也没有更好的解决方案。Hackerrank 的示例甚至更糟。

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

      1
       \
        14
       /  \
      3    15
     / \
    2   7
       /  \
      4     13
     / \   /
    5   6 10
         /  \
        8    11
         \    \
          9    12

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

- Gilbert

Answer 1

现在理解顶视图的定义的最佳方法是知道如何找到树的顶视图。

找到顶视图是两个遍历的组合，即层序遍历和垂直遍历（还有其他方法，但这是最基本的方法）。

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

就像你在注视树的顶部并开始画直线一样，直线首先切割的节点而不接触任何其他节点就是树的顶视图。

与Hackerrank上的所有其他问题一样，找到顶视图可以帮助您详细了解层序遍历和垂直遍历概念，从而加强您的基本概念。

- Shobhit Srivastava

Answer 2

为了回答你的问题，我要求你假设一个粗略的草图，才能真正理解问题顶部视图所询问的内容。你可以想象自己在直升机上从上方观察这棵树，而二叉树的根就像是一棵树的巅峰。

将根节点的等级设定为0。您需要按级别遍历树。如果向左走，则当前等级减1，而向右走则增加当前等级1。然后，您将能够看到每个等级的唯一值作为输出。

“等级”实际上是与“根节点”之间的“水平距离”。

就像在第一个示例中：

             ------- 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)

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

现在我想清楚了为什么5（排名=0）和6（排名=0）不在最终答案中。因为当从树的顶部看时，这些数字将被1（排名=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<<" ";
    }

}

上述问题的解决方案如下。 链接：解释得很清楚！逐步参考。 https://dev59.com/Ol0Z5IYBdhLWcg3wfge-#31388101

- eliee

Answer 3

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

想象一下你的树展开放在桌子上。从桌子的根端沿着它的长度向下看。假设节点的值写在小木块上，它们之间的链接由高到足以遮挡其后面的任何节点的木块表示，当你把头低到桌子高度时，你能看到哪些节点？在第一个例子中，5和6是隐蔽的，而2、3、4和7向左或向右延伸，以至于它们仍然可见。

然而，正如你的第二个例子所示，这是模棱两可的，无法确定节点2、5、11、12、13是否延伸得足够远以至于可见。

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

- soothsooth

Answer 4

我注意到没有人解释为什么你需要使用层序遍历而不是简单的任何其他递归遍历。

原因在于：二叉树可能具有倾斜的左子树，将其重叠在右子树下面或反之亦然，请看下面的示例。

A                     B
      1                  5
     / \                / \
    4   2              4   7
     \   \            /   /
      6   5          9   11
       \                /   
        3              13
         \            /
          11         7
           \        /
            2      3

如果您首先遍历左节点，则会在测试用例A中错误地编写右侧第一个w:node值，如果您首先开始遍历右节点，则测试用例B将失败。

只有逐层遍历才能保证存储正确的顶部视图值。

- Henadzi Rabkin

Answer 5

它运行良好且易于解决

import java.util.*;
import java.io.*;
class Node {
    Node left;
    Node right;
    int data;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class Solution {

    /*

    class Node
        int data;
        Node left;
        Node right;
    */
    class Nodegen
    {
        Node node;
        int gen;
        public Nodegen(Node node,int gen)
        {
            this.node=node;
            this.gen=gen;
        }
    }
    public static void topView(Node root) {
        Map<Integer,Nodegen> topview=new TreeMap<>();
        new Solution().printView(root,0,0,topview);
        //  System.out.print(topview.size());
        for (Map.Entry<Integer, Nodegen> entry : topview.entrySet()) {
            System.out.print(entry.getValue().node.data+" ");
        }


    }

    public  void printView(Node root,int align,int gen,Map<Integer,Nodegen> map) {
        if(root==null)
        {
            return ;
        }
        if(map.get(align)==null)
        {
            map.put(align,new Nodegen(root,gen));
        }else{
            if(map.get(align).gen>gen)
            {
                map.put(align, new Nodegen(root,gen));
            }
        }
        int temp=align+1;
        int temp1=align-1;
        int temp2=gen+1;
        printView(root.left,temp1,temp2,map);
        printView(root.right,temp,temp2,map);
    }

    public static Node insert(Node root, int data) {
        if(root == null) {
            return new Node(data);
        } else {
            Node cur;
            if(data <= root.data) {
                cur = insert(root.left, data);
                root.left = cur;
            } else {
                cur = insert(root.right, data);
                root.right = cur;
            }
            return root;
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        Node root = null;
        while(t-- > 0) {
            int data = scan.nextInt();
            root = insert(root, data);
        }
        scan.close();
        topView(root);
    }
}

- Nagappa L M