二叉树垂直遍历

https://www.lintcode.com/problem/651/solution/19792?utm_source=sc-libao-ql

描述

给定二叉树，返回其节点值的垂直遍历顺序。 (即逐列从上到下)。 如果两个节点在同一行和同一列中，则顺序应 从左到右。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

样例

样例1

输入： {3,9,20,#,#,15,7}输出： [[9],[3,15],[20],[7]]解释：   3  /\ /  \ 9  20    /\   /  \  15   7

样例2

输入： {3,9,8,4,0,1,7}输出：[[4],[9],[3,0,1],[8],[7]]解释：     3    /\   /  \   9   8  /\  /\ /  \/  \ 4  01   7

分析

用bfs一层层row来，每次左右子树按照col+1，col-1加入q。这里用map存col index，就可以不用担心负数index问题。

不用dfs，因为没办法保证row按顺序。

注意这里dict sort default by key.

```python
from typing import (
    List,
)
from lintcode import (
    TreeNode,
)
from collections import deque,defaultdict
"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: the root of tree
    @return: the vertical order traversal
    """
    def vertical_order(self, root: TreeNode) -> List[List[int]]:
        # write your code here
        q = deque()
        res = defaultdict(list)
        q.append((root,0))
        while q:
            node, col = q.popleft()
            if node:
                res[col].append(node.val)           
                q.append((node.left, col-1))          
                q.append((node.right, col+1))
        return [res[i] for i in sorted(res)]

```