Leetcode - 987-Vertical order traversal of binary trees

[Blog link]

The way to study ?

The nuggets home page

[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

• Breadth-first search

• Hash table

• Binary tree

• ? ? 0 129

[Topic link]

Leetcode title link

[making address]

Code link

[思路介绍]

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