问题描述

来源：LeetCode第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

问题分析

这题虽然是hard，但其实没有什么难度，做这题我最先想到的就是BFS遍历，如果当前节点是第m列，那么他的左子节点就是第m-1列，右子节点就是m+1列

所以我们可以从上到下一层一层的遍历，使用一个map来存储，map的key存储的是第几列，value是那个列的集合。辛辛苦苦写完之后发现运行不通过（代码放在了下面，有兴趣的可以看下），这是因为题中有这样一句话，如果同行同列上有多个结点，则按结点的值从小到大进行排序。也就是说如果两个节点位置重合了还要按照大小进行排序。

所以这题我们只能按照常规方式来解决，就是先记录下每个节点的值和坐标，最后再把他们按照同一列的顺序放到集合中，关于二叉树的遍历有多种，我们之前也介绍过一些

373，数据结构-6,树
488，二叉树的Morris中序和前序遍历

来看下代码

//错误的代码（同一行和同一列的两个值没有按照大小进行排序）



本文原创，未经作者允许不可转载！
更多内容，欢迎关注作者微信公众号：数据结构和算法！