1.问题
给你二叉树的根结点 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
2.解题思路
从示例可以得出，最终答案是先按列号从小到大排列，列号相同再按行号从小到大，行号相同再按值从小到大输出。因而我们在遍历二叉树时需要统计各个节点(列号，行号，值)的三元组，然后按照列号、行号、值的升序排列，最后输出结果。
- 定义一个map，key为节点，value存储该节点的列号，行号，值
- 深度优先算法，遍历各个节点，记录各节点 列号、行号、值，保存至map中
- 对map的values按照排序规则进行排序
复杂度：
- 时间复杂度：令总节点数量为 n，填充哈希表时进行树的遍历，复杂度为 O(n)；构造答案时需要进行排序，复杂度为 O(nlogn)。整体复杂度为 O(nlogn)
- 空间复杂度：O(n)
3.代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
//记录节点 列号、行号、值
Map<TreeNode, int[]> map = new HashMap<>();
public List<List<Integer>> verticalTraversal(TreeNode root) {
//示例规则，先按列号从小到大排列，列号相同再按行号从小到大，行号相同再按值从小到大输出
//定义一个map,key为节点，value存储该节点的 列号，行号，值
//深度优先算法，遍历各个节点，记录各节点 列号、行号、值，保存至map中
//对map的values按照排序规则进行排序
//root - map
map.put(root,new int[]{0,0,root.val});
dfs(root);
//各节点 遍历的信息列表
List<int[]> list=new ArrayList<>(map.values());
//排序
Collections.sort(list, (a,b)->{
//优先按列比较
if(a[0]!=b[0]){
return a[0]-b[0];
}
//其次 按行号比较
if(a[1]!=b[1]){
return a[1]-b[1];
}
//最后，按值比较
return a[2]-b[2];
});
//遍历list，输出结果集
List<List<Integer>> res=new ArrayList<>();
List<Integer> tmp;
for(int i=0;i<list.size();){
int j=i;
tmp=new ArrayList<>();
//列号相同的
while(j<list.size() && list.get(j)[0]==list.get(i)[0]){
tmp.add(list.get(j)[2]);
j++;
}
res.add(tmp);
i=j;
}
return res;
}
private void dfs(TreeNode node){
if(null==node){
return;
}
int[] nodeColRowVal=map.get(node);
int nodeCol=nodeColRowVal[0];
int nodeRow=nodeColRowVal[1];
int value=nodeColRowVal[2];
//左子树
if(null!=node.left){
map.put(node.left, new int[]{nodeCol-1, nodeRow+1, node.left.val});
dfs(node.left);
}
//右子树
if(null!=node.right){
map.put(node.right, new int[]{nodeCol+1, nodeRow+1, node.right.val});
dfs(node.right);
}
}
}
