与二叉树的顶视图的歧义

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

这是一个重要的言论。否，二进制树的顶视图并不重要，但定义了它。只是为这个问题而定义的临时概念，尽管它可能很有趣。

现在，可以有几种方法来定义二叉树的顶视图。没有明确的方式。这不是问题，只要运动/挑战/任务定义它，明确地定义它。但是，它是那个hackerrank问题没有清楚地定义这种模棱两可的概念。事实上，没有严格的定义。给出的例子有所帮助。事实上，这个问题及其在线法官希望我们以不同于我的第一反应的方式查看二叉树，以及史蒂文的解释！我会责怪这个问题的作者，谁是缺乏经验的，或者没有足够的注意创作问题。 （为了公平，他可能比我们更聪明和谨慎。然而，显然没有解决这个问题。无论如何，即使这个问题导致更多的伤害，我们也可以感谢他，即使这个问题导致更多的伤害。）

经验教训，再次学到：并非互联网上的所有资源都可靠或重要。

---

现在让我解释那个哈克兰克问题的意思，从预期的结果和问题测试仪的解决方案。

假设我们已经拥有了顶点之间的根，顶点和父儿童的形式的二叉树。例如，根部1，顶点1,2,3,4,5,6,7,8,9,10和5.left= 1，5.right= 10，1.Right= 2，10.left= 6 ，2.锐利= 3，6.right= 7，3.right= 4，7.right= 8，8.right= 9。 现在我们将根部放在0级的某个地方。

           5

. 现在我们在下面的下一个级别添加5,1和10的子项。左子女1将将一个单元移动到左侧。右孩子10，将被移动一个单位。

           5
        /     \
      1         10

.

现在放了1个孩子，然后，10个孩子在下一级别。如前所述，1,2的合适子将放置一个水平，一个单位对1.左子女10,6的左侧将被放置一个水平，一个单位左到10。由于该地方已经是这样占用2，我们刚刚在同一个地方放入2.然而，6被认为覆盖，由括号约为6。

           5
        /     \
      1         10
        \     /
          2(6)

.

现在我们把2和6个孩子放在下一级。请注意，7被覆盖，因为3优先。

           5
        /     \
      1         10
        \     /
          2(6)
              \
               3(7)

.

现在我们把3个和7个孩子放在一个下一级。请注意，涵盖8。

           5
        /     \
      1         10
        \     /
          2(6)
              \
               3(7)
                   \
                    4(8)

.

现在我们把4个和8个孩子放在一个下一级。嗯，因为4没有孩子，8,9的右孩子没有得到更多。

           5
        /     \
      1         10
        \     /
          2(6)
              \
               3(7)
                   \
                    4(8)
                        \
                          9

.

我们构建了二进制树的视觉表示。现在我们可以引用来自Hackerrank的原始语句，“顶视图意味着当您从顶部看树时，您将看到的是被称为树的顶视图。”顶视图是1,5,10,4,99，其他节点是覆盖，例如8，或由上方的节点阻挡，例如2和3，或两者，例如6和7。

问题中树的顶视图是2,14,15,12。

上面的图示应该足够清楚，因为它已经解释了所有尚不清楚的病例。鼓励读者制定严格的定义。

Answer 2

我认为他们正在尝试定义的是下面的。

给定rooted二进制树 $ t $ ，让 $ v（t）$ 是集 $ t $ 的顶点。对于 $ v \ v（g）$ ，let $ p_v $ 从根的唯一路径 $ t $ 到 $ v $ 。 我们将呼叫边缘 $（u，w）\在p_v $ a 左边缘，如果 $ w $ 是 $ u $ 的左子子，否则是右边缘。

let $ \ ell_v $ 和 $ r_v $ 是 $ P_V $ ，并定义 $ \ delta（v）=ell_v - r_v= 2 \ ell_v - | p_v | $ 。

let $ h（u）$ 是顶点 $ u $ $ t $ 和define $ \ delta（v）={\ delta_u \，：u \ in v（t）\ wedge h （U）。 顶视图 $ t $ 是set $ \ {v \ in v（t ）：\ delta_v \ not \ in \ delta（v）\} $ 。

在您的示例中，顶视图是 $ \ {1,2,12,14,15 \} $ 。一般而言，您可以计算 $ o（| v（t）|）$ 时间认为预订DFS访问。

我不知道为什么这很重要，抱歉。