好久没更新了，因为刚换了工作，比较忙。这次更新就由这道表面hard，实则medium的题目开始吧，同时希望自己的生活工作哪怕遇到hard，但也能积极面对，最后发现其实也就那回事！
审题：
给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。
对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。
二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。
返回二叉树的 垂序遍历 序列。
来源：力扣（LeetCode）
读完题目，应该还是很明白的，就是从左到右，从上到下，相同位置则从小到大，来对二叉树进行遍历
思考：
我们可以记录每个节点的位置信息，比如可以定义一个int[] a, a[0]记录x轴坐标，a[1]记录y轴坐标,a[2]记录节点的值，然后用一个list去储存这个a，最后对list按照上面的要求来进行排序即可，详细见代码和注释：
public List<List<Integer>> verticalTraversal(TreeNode root) { List<int[]> list = new ArrayList<>(); listNode(root, list, null, true); // 从左到右，从上到下，相同位置则从小到大进行排序 list.sort((o1, o2) -> { if (o1[0] != o2[0]) { return o1[0] - o2[0]; } else if (o1[1] != o2[1]) { return o1[1] - o2[1]; } else return o1[2] - o2[2]; }); List<List<Integer>> re = new ArrayList<>(); List<Integer> ll = new ArrayList<>(); // 进行分组，同一个x坐标则在一个组 for (int i = 0; i < list.size() - 1; i++) { ll.add(list.get(i)[2]); if (list.get(i)[0] != list.get(i + 1)[0]) { re.add(ll); ll = new ArrayList<>(); } } // 处理一下最右边的一个节点 ll.add(list.get(list.size() - 1)[2]); re.add(ll); return re; } /** * 进行递归先序遍历，为了通过父节点信息对子节点位置进行计算 * 定义一个int[3] 分别存x y val * * @param fa 父亲节点的位置信息 * @param b 左节点true 右节点false */ void listNode(TreeNode node, List<int[]> list, int[] fa, boolean b) { if (node == null) return; int[] a = new int[3]; // fa为null 的时候说明是父亲节点，那么x=0，y=0，默认值 if (fa != null) { if (b) { // 左节点x向左进行偏移一位 a[0] = fa[0] - 1; } else { // 右节点x向右进行偏移一位 a[0] = fa[0] + 1; } // 无论左右节点，y都要+1 a[1] = fa[1] + 1; } //保存节点值 a[2] = node.val; list.add(a); listNode(node.left, list, a, true); listNode(node.right, list, a, false); }
总结：
这道题思路还是很清晰的，一定要熟练掌握二叉树的遍历，尤其是进行遍历的时候，保存一些状态值。