二叉树顶视图的歧义

Question

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

我从我找到的文章中发现了很大的歧义和缺乏清晰度。

例如，这是用于演示geeksforgeeks上的顶视图的内容：

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

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

到目前为止，Stackoverflow示例也好不到哪里去。Hackerrank的例子更糟。

所以我希望有人能明确地告诉我顶视图是什么，因为我一直试图找出 2 天。例如，这棵树的顶视图是什么：

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

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

Answer 1

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

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

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

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

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