Binary Tree Vertical Order Traversal
要点：这题不难，就是要找到最简单的方法还需要有些考量。主要的原因是Tree的宽度是不知道的
- 用map记录min->max的区间，最后再iterate build返回数组。这样可以不用多traverse一遍Tree。
- traversal可以是dfs或者bfs
- dfs/bfs时候要存结点的pos（有一种类似解法是创建一个2d map[col][height]来存结点）。这个的意思就是left/right结点的pos是依赖于上一层的，而不是global的
效率：
- keys: 24.83% => 42.28%，for k in cols vs for k in cols.keys()
- next vs. counting: 42.28% => 58.39%
# 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]
# ]
# Given binary tree [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
# return its vertical order traversal as:
# [
# [4],
# [9,5],
# [3,0,1],
# [8,2],
# [7]
# ]
from collections import defaultdict, deque
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def verticalOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root: return []
cols = defaultdict(list)
q = deque([(root, 0)])
while q:
ql = len(q)
for _ in xrange(ql):
root, pos= q.popleft()
cols[pos].append(root.val)
if root.left:
q.append((root.left, pos-1))
if root.right:
q.append((root.right, pos+1))
return [cols[k] for k in xrange(min(cols.keys()), max(cols.keys())+1)]