651 · 二叉树垂直遍历

Inpurt:  {3,9,20,#,#,15,7}
Output: [[9],[3,15],[20],[7]]
Explanation:
   3
  /\
 /  \
 9  20
    /\
   /  \
  15   7

Input: {3,9,8,4,0,1,7}
Output: [[4],[9],[3,0,1],[8],[7]]
Explanation:
     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7

法 1 BFS

from typing import (
    List,
)
from lintcode import (
    TreeNode,
)

"""
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]]:
        if root is None:
            return []
        # 记录各节点的位置信息
        position = collections.defaultdict(list)
        queue = collections.deque()
        queue.append((root,0))
        while queue:
            cur_node, cur_pos = queue.popleft()
            position[cur_pos].append(cur_node.val)
            if cur_node.left:
                queue.append((cur_node.left, cur_pos-1))
            if cur_node.right:
                queue.append((cur_node.right, cur_pos+1))

        min_idx = min(position.keys())    
        res = []
        while position[min_idx]:
            res += [position[min_idx]]
            min_idx += 1

        return res