Java 中二叉树的底视图

在本节中，我们将学习如何使用不同的方法在 Java 中实现二叉树的底部视图。在二叉树的底部视图中，我们只打印当二叉树从底部查看时可见的那些节点。

例如，考虑以下二叉树。

底部视图是

注意：在二叉树的底部视图中，输出中节点的显示顺序并不重要。重要的是，所有从二叉树底部可见的节点都应包含在输出中。

方法 1：使用队列

我们进行层序遍历并将节点存储在队列中。我们假设根节点的水平距离 (horDis) 为 0，向下一层移动会将 horDis 更新为 -1，然后向右移动一步会将 horDis 更新为 +1。

请注意，在进行层序遍历时，我们还需要存储节点的水平距离。为了做到这一点，我们将使用一个 map，其中 horDis 是键，节点的数据是值。

实施

让我们看看使用队列实现二叉树底部视图的实现。

文件名： BottomViewExample.java

输出

10 5 25 14 7

方法 2：使用 HashMap()

在前一种方法中，我们讨论了使用队列实现二叉树的底部视图。在此方法中，我们使用了 Map，其中键是水平距离 (horDis)，值是 pair(k, r)，其中 r 表示节点的高度，k 表示节点的值。我们对二叉树进行前序遍历。如果当前节点是第一次观察到其水平距离，则将其插入 map。否则，我们会将当前节点与 map 中（在相同水平距离处）已存在的节点进行比较。如果当前节点的高度更大，则更新 map；否则，不更新。

实施

让我们看看使用 HashMap 实现二叉树底部视图的实现。

文件名： BottomViewExample1.java

输出

The following are the nodes present in the bottom view of the Binary Tree: 
25 14 7 10 5