data-structures - 二叉树顶 View 的歧义

Question

二叉树的顶 View 究竟是什么？

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

例如，这是用于演示 geeksforgeeks 上的顶 View 的内容。 :

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

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

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

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

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

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

Answer 1

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

找到顶 View 是两种遍历的组合，即-> Level Order Traversal 和 Vertical Traversal(也有其他方法，但这是最基本的)。

为了可视化这一点，开始在树中绘制垂直线，在您的第二个示例中，将绘制 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 的顶 View 。

就像您一直盯着树的顶部并开始绘制直线一样，直线在接触任何其他节点之前首先切割的节点是树的顶 View 。

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