# Question

Formatted question description: https://leetcode.ca/all/314.html

 314	Binary Tree Vertical Order Traversal

Given a binary tree, return the vertical order traversal of its nodes' values.
(ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Examples:
Given binary tree [3,9,20,null,null,15,7],

3
/ \
9  20
/  \
15   7
return its vertical order traversal as:

[
[9],
[3,15],
[20],
[7]
]

Given binary tree [3,9,20,4,5,2,7],

_3_
/   \
9    20
/ \   / \
4   5 2   7
return its vertical order traversal as:

[
[4],
[9],
[3,5,2],
[20],
[7]
]

@tag-tree


# Algorithm

How to determine the order of the columns, you can give the root node a sequence number of 0, and then start the traversal of the layer sequence. For any left child node, the sequence number is reduced by 1, and the right child node sequence number is increased by 1, so that the node value of the same column can be changed by the sequence number Put together

Another way, is to use a TreeMap to create a mapping between the sequence number and its corresponding node value.

• advantage of using TreeMap is that its automatic sorting function allows the column to be sorted from left to right. Since the sequence traversal needs to use the queue, the queue cannot only be stored at this time for nodes, it is necessary to store a pair consisting of a sequence number and a node, so that the sequence number can be operated every time it is taken out, and the nodes in the queue are also assigned their correct sequence numbers.

# Code

Java

TreeMap version

// Time complexity O(nlogn)
// Space complexity O(n)

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
Queue<Integer> cols = new LinkedList<>();
Map<Integer, List<Integer>> map = new TreeMap<>();
q.offer(root);
cols.offer(0);
int min = 0, max = 0;
while (!q.isEmpty()) {
TreeNode cur = q.poll();
int col = cols.poll();
if (!map.containsKey(col)) map.put(col, new ArrayList<>());
if (cur.left != null) {
q.offer(cur.left);
cols.offer(col - 1);
min = Math.min(min, col - 1);
}
if (cur.right != null) {
q.offer(cur.right);
cols.offer(col + 1);
max = Math.max(max, col + 1);
}
}