[LeetCode] 987. Vertical Order Traversal of a Binary Tree

Given a binary tree, return the vertical order traversal of its nodes values.

For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).

Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.

Example 1:

Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: 
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).

Example 2:

Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation: 
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.

Note:

The tree will have between 1 and 1000 nodes.
Each node's value will be between 0 and 1000.

二叉树的垂序遍历。

题意跟314题非常像，但是314只要求我们找到横坐标一样的元素，把他们合成一组；但是这个题的题设写的非常不清楚，根据test case，实际的要求是

如果是正常情况，自然就是从左往右按column输出所有节点；在每个column中，节点按照自身到根节点的距离由近到远输出
如果有两个节点的偏移量相同（应该是在同一个column里或一个是左孩子一个是右孩子），而且他们之于根节点的距离也相同，那么再按照node.val从小到大排序，比如例子中的5就在6的前面

这里我提供一个BFS的做法，思路跟314题也很像。这里我还是需要用到两个queue，一个存遍历的所有节点，一个存每个节点相对于根节点root的偏移量；我还需要一个总的hashmap和一个临时的hashmap temp。

之后按BFS的思路遍历整棵树，首先我们需要记录每一层的节点个数size，同时我们需要对同一层的节点进行一个局部的统计，用一个临时的hashmap temp记录每一层的节点的偏移量和节点信息。当前层遍历完毕之后，对于这个temp，我们把所有的节点拿出来并排序，把排序好的list再加入总的hashmap里，注意拿的方式是很巧妙的，因为我们在遍历一个hashmap的keySet的时候，key是按照被加入的顺序被读出来的，而且我们在存的时候，因为是BFS遍历所以基本顺序是根节点，左孩子，右孩子。所以key从temp里被读出来的基本顺序也是根节点，左孩子，右孩子，左孩子的孩子，右孩子的孩子。这个顺序也就隐性地满足了偏移量相同的时候的排序要求。其他环节跟314题基本相同。

时间O(nlogn)

空间O(n)

Java实现

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     public List<List<Integer>> verticalTraversal(TreeNode root) {
18         List<List<Integer>> res = new ArrayList<>();
19         // corner case
20         if (root == null) {
21             return res;
22         }
23 
24         // normal case
25         int min = 0;
26         int max = 0;
27         HashMap<Integer, List<Integer>> map = new HashMap<>();
28         Queue<TreeNode> queue = new LinkedList<>();
29         Queue<Integer> cols = new LinkedList<>();
30         queue.offer(root);
31         cols.offer(0);
32         while (!queue.isEmpty()) {
33             int size = queue.size();
34             HashMap<Integer, List<Integer>> temp = new HashMap<>();
35             for (int i = 0; i < size; i++) {
36                 TreeNode cur = queue.poll();
37                 int index = cols.poll();
38                 if (!temp.containsKey(index)) {
39                     temp.put(index, new ArrayList<>());
40                 }
41                 temp.get(index).add(cur.val);
42                 min = Math.min(min, index);
43                 max = Math.max(max, index);
44                 if (cur.left != null) {
45                     queue.offer(cur.left);
46                     cols.offer(index - 1);
47                 }
48                 if (cur.right != null) {
49                     queue.offer(cur.right);
50                     cols.offer(index + 1);
51                 }
52             }
53             // 在这里sort是因为深度不同的时候，深度小的在前
54             // 深度相同的时候val小的在前
55             for (int key : temp.keySet()) {
56                 if (!map.containsKey(key)) {
57                     map.put(key, new ArrayList<>());
58                 }
59                 List<Integer> list = temp.get(key);
60                 Collections.sort(list);
61                 map.get(key).addAll(list);
62             }
63         }
64 
65         for (int i = min; i <= max; i++) {
66             List<Integer> list = map.get(i);
67             res.add(list);
68         }
69         return res;
70     }
71 }