Java 中二叉树的垂直序遍历

在本节中，我们将讨论 Java 中二叉树的垂直序遍历 以及实现它的不同方法。在垂直序遍历中，我们从上到下垂直打印二叉树的节点。例如，考虑以下二叉树。

垂直序遍历结果是

方法 1：使用水平距离

在这种方法中，我们只遍历一次树，并将根作为参考点，找到最大和最小水平距离。假设二叉树的根节点位于距离 0 的位置。同样，假设向左走一步是 -1，向右走一步是 +1。对于上述二叉树，最小距离是 -2（值为 1 的节点），最大距离是 3（值为 19 的节点）。

在找到根节点到各节点的最小和最大距离后，遍历范围从最小距离到最大距离的每一条垂直线。在遍历每一条垂直线时，打印位于该垂直线上的节点（参见上图）。

实施

让我们看一下使用水平距离方法实现二叉树垂直序遍历的示例。

文件名： VerticalTraversalExample.java

输出

The vertical order traversal of the binary tree is:
1 
2 
4 3 6 
5 18 
7 
19   

时间复杂度： 上述算法的时间复杂度为 O(wid * no)，其中“wid”是给定二叉树的宽度，“no”是二叉树中的节点数。在最坏的情况下，wid 的值可以是 O(no)（例如，考虑一个完全二叉树），在这种情况下，时间复杂度可以变为 O(no²）。

方法 2：使用 TreeMap

在前一种方法中，我们讨论了一种 O(no²) 的解决方案。在这种方法中，我们将使用 TreeMap，它能提供比 TreeMap 更好的解决方案。在这种方法中，也需要通过以根节点为参考点来检查所有节点的水平距离。与前一种方法类似，当我们移动到一个比根节点左边一个单位的节点时，水平距离被视为 -1。对于根节点的右侧节点，水平距离被视为 +1。在执行树的先序遍历时，我们可以计算水平距离。对于每个水平距离值，TreeMap 中都会维护一个节点列表。

实施

让我们看一下使用 TreeMap 实现二叉树垂直序遍历的示例。

文件名： VerticalTraversalExample1.java

输出

The vertical order traversal of the binary tree is:
[1]
[2]
[4, 3, 6]
[5, 18]
[7]
[19]    

时间复杂度： 上述解决方案基于哈希技术，其时间复杂度被认为是 O(n)，其中 n 是二叉树中的总节点数。请注意，当使用良好的哈希方法来实现 O(1) 的检索和插入操作时，可以达到 O(n) 的时间复杂度。

方法 3：使用层序遍历

可以使用 层序遍历 的概念来实现二叉树的垂直序遍历。我们借助队列来遍历节点。队列的每个元素都提供有关水平距离和二叉树节点的信息。

与其他方法类似，在此方法中，我们也通过将树的根节点作为参考点来查找水平距离。同样，从根节点向左移动会在每个连续节点上加 -1。类似地，从根节点向右移动会在每个连续节点上加 +1。在完成树的层序遍历后，我们逐个弹出队列中的元素。

如上图所示的垂直线可以被视为节点所在的层。可以通过水平距离 (horDis) 来确定哪个节点位于同一垂直线上。我们可以将这些节点放入一个 ArrayList 中，并且列表的对应项将是水平距离。我们将列表和水平距离放入一个 Map 中。最后，我们遍历 Map 来显示结果。

实施

让我们看一下使用层序遍历实现二叉树垂直序遍历的示例。

文件名： VerticalTraversalExample1.java

输出

The vertical order traversal of the binary tree is: 
1 
2 
4 3 6 
5 18 
7 
19   

时间复杂度： 上述程序的时间复杂度为 O(n)，其中 n 是树中的总节点数。