• ㊗️
• 大家
• offer
• 多多！

## Problem

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

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

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

Output:

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


Examples 2:

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

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

Output:

[
[4],
[9],
[3,0,1],
[8],
[7]
]


Examples 3:

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


Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

## Code

655. Print Binary Tree

class Solution {
int min = 0;
int max = 0;
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res =  new ArrayList<>();
if (root == null) return res;
helper(root, 0);

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

queue.offer(root);
index.offer(-min);

while(!queue.isEmpty()){
TreeNode curr = queue.poll();
int currIndex = index.poll();
if (curr.left != null) {
queue.offer(curr.left);
index.offer(currIndex - 1);
}

if (curr.right != null) {
queue.offer(curr.right);
index.offer(currIndex + 1);
}
}
return res;
}

// 找到树的最左边和最右边
private void helper(TreeNode root, int index){
if(root == null) return;
min = Math.min(min, index);
max = Math.max(max, index);
helper(root.left, index - 1);
helper(root.right, index + 1);
}
}