# 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,8,4,0,1,7],
>
> ```
>  3
>
> /\
> ```
>
> / \\
>
> 9 8
>
> / /\\
>
> / \\/ \\
>
> 4 01 7
>
> return its vertical order traversal as:
>
> \[
>
> \[4],
>
> \[9],
>
> \[3,0,1],
>
> \[8],
>
> \[7]
>
> ]

## Thoughts

纵向遍历二叉树，结点最多的那层最左结点为起始层。把root所在纵向坐标看作0，其它结点存与它的相对坐标，即左叶子为parent - 1, 右+1，然后按层遍历。

## Code

```cpp
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: the root of tree
     * @return: the vertical order traversal
     */
    vector<vector<int>> verticalOrder(TreeNode * root) {
        if (root == nullptr) return vector<vector<int>>();
        queue<pair<TreeNode*, int>> q;
        q.push({root, 0});
        unordered_map<int, vector<int>> m;
        int mi = 0, mx = 0;
        while (!q.empty()) {
            const auto t = q.front();
            q.pop();
            m[t.second].push_back(t.first->val);
            mi = min(mi, t.second);
            mx = max(mx, t.second);
            if (t.first->left != nullptr) q.push({t.first->left, t.second - 1});
            if (t.first->right != nullptr) q.push({t.first->right, t.second + 1});
        }
        vector<vector<int>> res;
        for (int i = mi; i <= mx; ++i) {
            res.push_back(m[i]);
        }
        return res;
    }
};
```

## Analysis

时间复杂度O(N), N为结点数.