LeetCode二叉树的垂序遍历

题目描述

给你二叉树的根结点 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 在此列中。

987. 二叉树的垂序遍历

解题思路

首先本题是一道困难题，其解决方法并不难想，主要难度主要集中在实现的细节。对于相同列的排序，行小的在前，同行的按照从大到小排序，所以这个实现我想到了java的排序器，制定类的规则。这个问题想好就按照dfs进行一次遍历，主要记录行列，将同列的放入同一个List从而进行排序，整体实现思路并不复杂，主要需要看清楚题意并认真实现。

具体实现，代码如下

class Solution {public List<List<Integer>> verticalTraversal(TreeNode root) {Map<Integer, List<Node>> map = new HashMap<>();List<List<Integer>> lists = new ArrayList<>();List<Integer> list = new ArrayList<>();dfs(0, 0, root, map, list);Collections.sort(list);//进行排序for (int i : list) {Collections.sort(map.get(i));List<Integer> l = new ArrayList<>();for (Node n : map.get(i))l.add(n.val);lists.add(l);}return lists;}public void dfs(int c, int r, TreeNode p, Map<Integer, List<Node>> map, List<Integer> list) {if (p != null) {if (!map.containsKey(c)) {list.add(c);map.put(c, new ArrayList<Node>());}map.get(c).add(new Node(r, p.val));dfs(c - 1, r + 1, p.left, map, list);dfs(c + 1, r + 1, p.right, map, list);}}
}class Node implements Comparable<Node> {int r;int val;Node(int r, int val) {this.r = r;this.val = val;}public int compareTo(Node o) {//排序器if (this.r > o.r) {return 1;} else if (this.r < o.r) {return -1;} else {if (this.val > o.val)return 1;else if (this.val < o.val)return -1;elsereturn 0;}}
}