题目
给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。
对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。
二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。
返回二叉树的 垂序遍历 序列。
思路
- 二叉树dp的方式收集树上的信息，info(col,row,val)
- 通过col，row，val的从小到大排序树上的节点信息
- 整合信息：如果col一样的放在一个list中, 并返回结果
解法
public List<List<Integer>> verticalTraversal(TreeNode root) {
if(root == null){
return null;
}
//1.收集整棵的信息，存在resultList
List<Info> resultList = new ArrayList<>();
process(root, true, null, resultList);
//2.通过col，row，val的从小到大排序，树上的节点信息
Collections.sort(resultList, new Comparator<Info>() {
@Override
public int compare(Info o1, Info o2) {
if(o1.col != o2.col){
return o1.col - o2.col;
}else if(o1.row != o2.row){
return o1.row - o2.row;
}else {
return o1.val - o2.val;
}
}
});
//3.整合信息：如果col一样的放在一个list中
List<List<Integer>> ans = new ArrayList<>();
int lastCol = Integer.MAX_VALUE;
int i = 0;
for (Info info : resultList) {
if (info.col != lastCol) {
lastCol = info.col;
ans.add(new ArrayList<>());
i++;
}
ans.get(i - 1).add(info.val);
}
return ans;
}
public void process(TreeNode node, boolean left, Info rootInfo, List<Info> resultList){
if(node == null){
return;
}
Info nodeInfo;
//收集自己的信息
if(rootInfo == null ){
nodeInfo = new Info(0,0, node.val);
}else {
if(left){
nodeInfo = new Info(rootInfo.row + 1, rootInfo.col - 1, node.val);
}else{
nodeInfo = new Info(rootInfo.row + 1, rootInfo.col + 1, node.val);
}
}
resultList.add(nodeInfo);
//收集子树的信息
process(node.left, true, nodeInfo, resultList);
process(node.right, false, nodeInfo, resultList);
}
static class Info{
private int val;
private int col;
private int row;
public Info(int row, int col ,int val){
this.col = col;
this.row = row;
this.val = val;
}
}
