10月24号面的fb。面试官是湾区白人小哥，出题难度中等。

1. 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 .

``````Input: [3,9,20,null,null,15,7]

3
/\
/  \
9  20
/\
/  \
15   7

Output:

[
[9],
[3,15],
[20],
[7]
]
``````
``````Input: [3,9,8,4,0,1,7]

3
/\
/  \
9   8
/\  /\
/  \/  \
4  01   7

Output:

[
[4],
[9],
[3,0,1],
[8],
[7]
]
``````
``````Input: [3,9,8,4,0,1,7,null,null,null,2,5] (0's right child is 2 and 1's left child is 5)

3
/\
/  \
9   8
/\  /\
/  \/  \
4  01   7
/\
/  \
5   2

Output:

[
[4],
[9,5],
[3,0,1],
[8,2],
[7]
]
``````
1 Like

The following solution takes `5ms` .

• BFS, put `node` , `col` into queue at the same time
• Every left child access `col - 1` while right child `col + 1`
• This maps `node` into different `col` buckets
• Get `col` boundary `min` and `max` on the fly
• Retrieve `result` from `cols`

Note that `TreeMap` version takes `9ms` .

Here is an example of `[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]` . Notice that every child access changes one column bucket id. So `12` actually goes ahead of `11` .

``````public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}

Map<Integer, ArrayList<Integer>> map = new HashMap<>();

int min = 0;
int max = 0;

while (!q.isEmpty()) {
TreeNode node = q.poll();
int col = cols.poll();

if (!map.containsKey(col)) {
map.put(col, new ArrayList<Integer>());
}

if (node.left != null) {
min = Math.min(min, col - 1);
}

if (node.right != null) {
max = Math.max(max, col + 1);
}
}

for (int i = min; i <= max; i++) {
}

return res;
}
``````
3 Likes

Alternatively, we can calculate the rang first, then insert into buckets.

``````public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> cols = new ArrayList<>();
if (root == null) {
return cols;
}

int[] range = new int[] {0, 0};
getRange(root, range, 0);

for (int i = range[0]; i <= range[1]; i++) {
}

while (!queue.isEmpty()) {
TreeNode node = queue.poll();
int col = colQueue.poll();

if (node.left != null) {
}
if (node.right != null) {
}
}

return cols;
}

public void getRange(TreeNode root, int[] range, int col) {
if (root == null) {
return;
}
range[0] = Math.min(range[0], col);
range[1] = Math.max(range[1], col);

getRange(root.left, range, col - 1);
getRange(root.right, range, col + 1);
}

``````
1 Like