# Leetcode daily problem series - vertical order of binary tree traversal

Posted on Dec. 3, 2022, 8:06 a.m. by Benjamin Stevens
Category: The back-end

# Leetcode - 987-Vertical order traversal of binary trees

The way to study ?

## [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

• Depth-first search

• Hash table

• Binary tree

• ? ? 0 129

## [思路介绍]

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))

Search