987. 二叉树的垂序遍历

题目描述：

给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

返回二叉树的 垂序遍历 序列。

示例1：

输入：root = [3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]
解释：
列 -1 ：只有结点 9 在此列中。
列  0 ：只有结点 3 和 15 在此列中，按从上到下顺序。
列  1 ：只有结点 20 在此列中。
列  2 ：只有结点 7 在此列中。

示例2：

输入：root = [1,2,3,4,5,6,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
列 -2 ：只有结点 4 在此列中。
列 -1 ：只有结点 2 在此列中。
列  0 ：结点 1 、5 和 6 都在此列中。
          1 在上面，所以它出现在前面。
          5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。
列  1 ：只有结点 3 在此列中。
列  2 ：只有结点 7 在此列中。

示例3：

输入：root = [1,2,3,4,6,5,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。
因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。

提示：

• 树中结点数目总数在范围 [1, 1000] 内
• 0 <= Node.val <= 1000

---

解题分析及思路：

方法一：深度优先搜索 + 排序

我们可以通过一次遍历整棵树，并使用数组 nodes 记录每个节点的行号 row、列号 col 以及值 val。

遍历完成后，我们按照 col 为第一关键字升序，row 为第二关键字升序，val 为第三关键字升序，对所有节点进行排序。

在排序完成后，我们需要按照题目要求，将同一列的所有节点放入同一个数组中。因此，对 nodes 进行一次遍历，并在遍历的过程中记录上一个节点的列号 lastCol。

• 如果当前遍历到的节点的列号 col 与 lastCol 相等，则将该节点放入与上一个节点相同的数组中；
• 否则放入不同的数组中。

func verticalTraversal(root *TreeNode) (ans [][]int) {
	type Pair struct {
		val, row, col int
	}
	var data []Pair
	var dfs func(node *TreeNode, row int, col int)
	dfs = func(node *TreeNode, row int, col int) {
		if node != nil {
			data = append(data, Pair{
				node.Val, row, col,
			})
			dfs(node.Left, row+1, col-1)
			dfs(node.Right, row+1, col+1)
		}
	}
	dfs(root, 0, 0)
	sort.Slice(data, func(i, j int) bool {
		return data[i].col < data[j].col || data[i].col == data[j].col && (data[i].row < data[j].row || data[i].row == data[j].row && data[i].val < data[j].val)
	})

	lastCol := math.MinInt32
	for _, node := range data {
		if node.col != lastCol {
			lastCol = node.col
			ans = append(ans, nil)
		}
		ans[len(ans)-1] = append(ans[len(ans)-1], node.val)
	}
	return
}

复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(N)

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:2.6 MB,击败了22.32% 的Go用户