Binary Tree Vertical Order Traversal

此题还是二叉树和哈希表结合的问题，和leaves那题有异曲同工之处，区别在于这里不是用高度来进行分类而是通过列数，所谓列数也就是将根节点设为列数0，往左遍历列数减1，往右加1即可，这也是这道题巧妙的地方，至于每层的顺讯，通过观察示例输出我们可以看出这里应该使用层级遍历来保证每层的顺序不乱

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
class Solution:
    # @param {TreeNode} root the root of binary tree
    # @return {int[][]} the vertical order traversal
    def verticalOrder(self, root):
        # Write your code here
        if not root:
            return []

        store = {}

        q, cur, nxt = collections.deque([[root, 0]]), 1, 0
        while q:
            node, col = q.pop()
            cur -= 1
            store.setdefault(col, [])
            store[col].append(node.val)
            if node.left:
                q.appendleft([node.left, col - 1])
                nxt += 1
            if node.right:
                q.appendleft([node.right, col + 1])
                nxt += 1
            if not cur:
                cur, nxt = nxt, cur

        result = []
        for key in sorted(store.keys()):
            result.append(store[key])

        return result

上面因为哈希表无序的原因，我们对key进行了排序导致时间复杂度上升到了O(nlgn)，但是如果我们记录最小和最大的level数，就可以只用O(n)的时间把所有结果有序收集起来了

class Solution(object):
    def verticalOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []

        store = collections.defaultdict(list)
        queue = collections.deque([[root, 0]])
        result = []
        cur, nxt = 1, 0
        minLevel, maxLevel = 0, 0

        while queue:
            node, level = queue.pop()
            minLevel = min(minLevel, level)
            maxLevel = max(maxLevel, level)
            cur -= 1
            store[level].append(node.val)
            if node.left:
                queue.appendleft([node.left, level - 1])
                nxt += 1
            if node.right:
                queue.appendleft([node.right, level + 1])
                nxt += 1
            if not cur:
                cur, nxt = nxt, cur

        for i in xrange(minLevel, maxLevel + 1):
            result.append(store[i])

        return result