Binary Tree Vertical Order Traversal

Given a binary tree, return thevertical ordertraversal 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:

1. 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]
]

2.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]
]

1. 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]
]

这道题让我们竖直遍历二叉树，并把每一列存入一个二维数组，我们看题目中给的第一个例子，3和15属于同一列，3在前，第二个例子中，3,5,2在同一列，3在前，5和2紧随其后，那么我们隐约的可以感觉到好像是一种层序遍历的前后顺序，那么我们如何来确定列的顺序呢，我们可以把根节点给个序号0，然后开始层序遍历，凡是左子节点则序号减1，右子节点序号加1，这样我们可以通过序号来把相同列的节点值放到一起，我们用一个map来建立序号和其对应的节点值的映射，用map的另一个好处是其自动排序功能可以让我们的列从左到右，由于层序遍历需要用到queue，我们此时queue里不能只存节点，而是要存序号和节点组成的pair，这样我们每次取出就可以操作序号，而且排入队中的节点也赋上其正确的序号

# 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]]
        """
        """
        this problem seemed very hard but actually once you draw a picture on a paper or in your brain, it becomes pretty clear.
        - for the left  node, you set its index as index - 1
        - for the right node, you set its index as index + 1
        - use queue to loop through all the nodes in a tree
        - set index as a key to the hashmap() and value as a list of vals
        - add node.data into hashmap() with index as a key
        - keep track of min and max index and store into solution list and return it
        """
        if not root:
            return []
        minindex, maxindex = 0, 0
        result = []
        hashmap = {}
        queue = [(root, 0)]

        while queue:
            node, index = queue.pop(0)
            if index in hashmap:
                hashmap[index].append(node.val)
            else:
                hashmap[index] = [node.val]

            if node.left:
                queue.append((node.left, index-1))
                minindex = min(minindex, index-1)
            if node.right:
                queue.append((node.right, index+1))
                maxindex = max(maxindex, index+1)

        for i in xrange(minindex, maxindex+1):
            result.append(hashmap[i])
        return result