以垂直顺序打印二叉树

给定一个二叉树，以垂直顺序打印它。下面的示例演示了垂直顺序遍历。

目标是遍历一次树，测量根节点到各节点的最小和最大水平距离。上述图中节点的最小距离为 -2（值为 4 的节点），最大距离为 3（值为 9 的节点）。

在确定了根节点到各节点的最小和最大距离后，我们从最小到最大距离的每一条垂直线重复此过程，为每一条垂直线遍历树，并输出沿该垂直线的节点。

算法

C++ 代码

上述算法的实现如下。

输出

Vertical order traversal is 
4 
2 
1 5 6 
3 8 
7 
9 

时间复杂度：上述方法的时间复杂度为 O(w*n)，其中 w 是二叉树的宽度，n 是节点数。在最坏情况下，w 的值可能为 O(n)（以满二叉树为例），时间复杂度可能增加到 O(n^2)。

本文介绍的方法可以更有效地解决这个问题。稍后，我们将讨论完整的算法以及如何实践更有效的方法。

方法 -2 - 优化方法：（使用最小堆）

算法

• 在这种情况下，需要进行定制的遍历。
• 如果我们按照上图所示的方式对垂直线进行编号。
• 需要按垂直线索引升序、层索引升序、以及在垂直线索引和层索引相同时按层序遍历升序进行遍历。
• 因此，我们需要四个因子：垂直线索引、层索引、层序遍历（BFS）序号和节点值。
• 垂直索引编号从根节点的 0 开始。
  • 如果向左走，V = V - 1
  • 如果向右走，v = v+1。（请参阅图以更详细地解释原因。）
• 层索引 = 从根节点的 0 开始。
  • 无论向左还是向右，我们都只向下移动一层，所以 l = l+1。
• 进行层序遍历，并将弹出的节点以上述更改存储在 MINHEAP 中。
• 从 MINHEAP 中弹出后直接打印即可。
• 当到达下一条垂直线时，如有必要，打印一个换行符。

注意

• 为什么使用 MinHeap？因为我们需要升序，最小值优先。
• 我们使用 pair<pair<int,int>,pair<int,int>> 来存储所有 4 个参数 {{ },{ }}

C++ 代码

上述算法的实现如下。

输出

Vertical order traversal is 
4 
2 
1 5 6 
3 8 
7 
9 

时间复杂度：O(N*LogN) 时间

原因

• 普通的层序（BFS）遍历需要 O(N)。
• 但在这里，我们正在将元素推入 MinHeap - 单次推操作需要 O(LogN)。
• 因此，总时间复杂度为 O(N*LogN)。
• 同样，从 minHeap 中弹出也需要 O(N*LogN)。

辅助空间：O(N)

原因

• 队列在最后一层最多会包含 O(N/2) = O(N) 个元素。
• 堆在某个时刻也会存储所有节点，所以是 O(N)。

N 是二叉树的大小。（节点的总数）