二叉树的顶视图

二叉树

二叉树是一种非线性数据结构，其中每个父节点最多有两个子节点。

二叉树中的每个节点除了数据元素外，还包含左子节点和右子节点的引用。树形结构顶端的节点称为根节点。包含其他子节点的节点称为父节点。

父节点的两个子节点称为左子节点和右子节点。哈希、数据压缩、网络流量路由、二叉堆的建立和二叉搜索树的构建等都使用了二叉树。

顶部视图

二叉树中的节点相互连接，使得每个节点最多可以有两个子节点。

从上方俯视时可以看到的节点就是顶部视图节点。为了打印二叉树的顶部视图，我们可以按任何顺序打印节点。

二叉树的顶部视图是指从顶部观察树时可以看到的节点集合。对于下图所示的树

示例

4 2 1 3 7 将会出现在顶部。因此，顶部视图将是：4 2 1 3 7。

方法

策略是使用前序遍历遍历树，检查当前垂直级别是否已被访问，如果已被访问，则查找更小的水平级别节点并存储。如果未被访问，则可以直接更新已访问的垂直级别并存储当前节点的节点和水平级别。

由于映射将显示节点相对于根节点的水平距离，因此我们可以使用它来确定是否已经达到水平级别。其中键代表水平距离，值是每个节点的数值和级别组成的对。

将使用前序遍历来导航树。

每次我们确定当前水平距离的级别是否小于先前观察到的最高级别时，都会更新此水平距离的值和级别。

为了获得垂直级别，我们必须将左子节点的级别传递为 1，将右子节点的级别传递为 level + 1。

在映射中打印存在的值。

C++ 程序

Input:
      1
   /    \
  2      3
Output: 
2 1 3

Java 程序

输出

Input:
      1
   /    \
  2      3
Output: 
2 1 3

Python 程序

输出

Input:
      1
   /    \
  2      3
Output: 
2 1 3

时间复杂度：O(N)，其中 N 是数组的大小，是时间复杂度。

空间复杂度：O(1)

如何找到树的顶部视图？

为了在递归查找的同时存储每个节点与根节点之间的水平距离，我们必须首先识别从顶部可见的节点。

树的顶部视图由从顶部观察树时可以看到的节点组成。