## 题目

Given a binary tree, return the vertical order traversal of its nodes values.

For each node at position `(X, Y)`

, its left and right children respectively will be at positions `(X-1, Y-1)`

and `(X+1, Y-1)`

.

Running a vertical line from `X = -infinity`

to `X = +infinity`

, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing `Y`

coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of `X`

coordinate. Every report will have a list of values of nodes.

Example 1:

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

Example 2:

1 | Input: [1,2,3,4,5,6,7] |

**Note:**

- The tree will have between
`1`

and`1000`

nodes. - Each node’s value will be between
`0`

and`1000`

.

## 思路

DFS.

I have a dictionary with the keys: `x`

and the value: `a tuple of (y, root.val)`

. I then sort the dictionary based on keys and sort it again based on y.

## 代码

1 | # Definition for a binary tree node. |