【递归】987. 二叉树的垂序遍历（困难）
让我们先来看看这道题目的描述
这道题目思路比较简单
遍历这棵树，记录每一个节点的所在的列位置，所在的行位置，以及这个节点的值，根据先考虑列，再考虑行，最后再考虑节点的value进行排序
按照不同的列，进行分组，最后返回答案
/*** 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{public List<List<Integer>> verticalTraversal(TreeNode root) {List<List<Integer>> ans = new ArrayList<>();List<int[]> info = new ArrayList<>();save(root, 0, 0, info);Collections.sort(info, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] 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];}});int visited = Integer.MIN_VALUE;for(int[] in : info){if(in[0] != visited){visited = in[0];ans.add(new ArrayList<>());}ans.get(ans.size() - 1).add(in[2]);}return ans;}private void save(TreeNode node, int col, int row, List<int[]> info){if(node == null) return;info.add(new int[] {col, row, node.val});save(node.left, col - 1, row + 1, info);save(node.right, col + 1, row + 1, info);}}
也可以用一张哈希表来存储节点和对应的信息，因为二叉树遍历后，哈希表的key将不再被使用，所以不用哈希表也可以～