Leetcode daily problem series  vertical order of binary tree traversal
Leetcode  987Vertical order traversal of binary trees
[Blog link]
[Topic description]
Give you the root of the binary tree root, please design an algorithm to calculate the vertical order traversal sequence of the binary tree.
For each node located in (row, col), the left and right children are located in (row + 1, col 1) and (row + 1, col + 1). The root of the tree is at (0, 0).
The vertical order traversal of the binary tree starts from the leftmost column to the rightmost column, and indexes all nodes in each column by column, forming an ordered list in order of occurrence from top to bottom. If there are more than one node in the same row in the same column, the node value is sorted from smallest to largest.
Returns the vertically ordered traversal sequence of a binary tree.
Example 1:
Input: root = [3,9,20,null,null,15,7] output: [[9],[3,15],[20],[7] explanation: column 1: only node 9 is in this column. Column 0: Only nodes 3 and 15 are in this column, in top to bottom order. Column 1: Only node 20 is in this column. Column 2: Only node 7 is in this column.Copy the code
Example 2:
Output: input: root =,2,3,4,5,6,7 [1], [[4], [2], [1 and 6], [3], [7]] :  2:4 only nodes in this column. Column 1: Only node 2 is in this column. Column 0: nodes 1, 5, and 6 are in this column. 1 is up here, so it appears in front. Both the 5 and 6 positions are (2, 0), so order from smallest to largest, with 5 coming before 6. Column 1: Only node 3 is in this column. Column 2: Only node 7 is in this column.Copy the code
Example 3:
Input: root = [1,2,3,4,6,5,7] output: [[4],[2],[1,5,6],[3],[7] Because the 5 and 6 are still in the same position, the answer remains the same, and the values are still sorted from smallest to largest.Copy the code
Tip:
 The total number of nodes in the tree is in range
[1, 1000]
内 0 = Node.val = 1000
Related Topics

The tree

Depthfirst search

Breadthfirst search

Hash table

Binary tree

? ? 0 129
[Topic link]
[making address]
[思路介绍]
Idea 1: DFS+ priority queue +hash
 The overall difficulty is actually not that high
 The list of corresponding column elements is stored by hash, and the key is the column index
 Eject the order of elements in each column through a priority queue
 I forgot that the priority queue is just a popup order effect, and that the storage doesn't actually change the order outside the top of the heap
Class Solution {// List list Integer res = new ArrayList(); MapInteger, PriorityQueueIndex map = new TreeMap(new ComparatorInteger() { @Override public int compare(Integer o1, Integer o2) { return o1  o2; }}); public ListListInteger verticalTraversal(TreeNode root) { //corner case if (root == null) { return null; } dfs(root, 0, 0); for (Integer key : map.keySet() ) { PriorityQueueIndex priorityQueue = map.get(key); ListInteger ans = new ArrayListInteger(); while (! priorityQueue.isEmpty()){ ans.add(priorityQueue.poll().val); } res.add(ans); } return res; } private void dfs(TreeNode root, int col, int row) { if (root == null) { return; } PriorityQueue = new PriorityQueue(new ComparatorIndex() {@override public int compare(Index o1, Index o2) { if (o1.x == o2.x) { return o1.val  o2.val; } else { return o1.x  o2.x; }}}); if (map.containsKey(col)) { priorityQueue = map.get(col); } priorityQueue.add(new Index(row, root.val)); map.put(col, priorityQueue); dfs(root.left, col  1, row + 1); dfs(root.right, col + 1, row + 1); }} class Index {int x; int val; public Index(int x, int val) { this.x = x; this.val = val; } public int getX() { return x; } public int getVal() { return val; } public void setVal(int val) { this.val = val; } public void setX(int x) { this.x = x; }}Copy the code
O(NLG (n))O(NLG (n))O(NLG (n))