Binary Tree Vertical Order Traversal

题目地址：
https://leetcode.com/problems/binary-tree-vertical-order-traversal/#/description

题目：

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:

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

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

题目分析：
这道题主要思想是运用bfs+treeMap。使用queue来实现bfs。其中map是为了保存某个index对应的所有元素。然后queue是为了将bfs的Pair对(index + node)的组合存起来。

代码：

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}
class Pair {
    TreeNode node;
    int index;
    public Pair(TreeNode n, int i) {
        node = n;
        index = i;
    }
}
TreeMap<Integer, List<Integer>> treeMap = new TreeMap<>();

public List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> rst = new ArrayList<>();
    Queue<Pair> q = new LinkedList<>();
    if(root == null){
        return rst;
    }
    q.add(new Pair(root, 0));
    while(!q.isEmpty()){
        Pair curr = q.poll();
        if(!treeMap.containsKey(curr.index)){
            treeMap.put(curr.index, new ArrayList<>());
        }
        treeMap.get(curr.index).add(curr.node.val);
        if(curr.node.left != null){
            q.offer(new Pair(curr.node.left, curr.index - 1));
        }
        if(curr.node.right != null){
            q.offer(new Pair(curr.node.right, curr.index + 1));
        }
    }
    for(int key : treeMap.keySet()){
        rst.add(treeMap.get(key));
    }
    return rst;
}