My code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }
        
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        Queue<Integer> cols = new LinkedList<Integer>();
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        q.offer(root);
        cols.offer(0);
        
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode curr = q.poll();
                int col = cols.poll();
                if (!map.containsKey(col)) {
                    map.put(col, new ArrayList<Integer>());
                }
                map.get(col).add(curr.val);
                if (curr.left != null) {
                    q.offer(curr.left);
                    cols.offer(col - 1);
                }
                if (curr.right != null) {
                    q.offer(curr.right);
                    cols.offer(col + 1);
                }
            }
        }
        
        int[] colArr = new int[map.keySet().size()];
        int counter = 0;
        for (Integer temp : map.keySet()) {
            colArr[counter++] = temp;
        }
        Arrays.sort(colArr);
        for (int i = 0; i < colArr.length; i++) {
            ret.add(map.get(colArr[i]));
        }
        
        return ret;
    }
}

看了題目覺得完全沒思路。。。即使知道要用hashmap
后來看了答案才知道，可以給每個結(jié)點(diǎn)編一個列號，col
col可以是正數(shù)，也可以是負(fù)數(shù)，也可以是0，沒關(guān)系，只是作為hashmap的一個key
所以，如果一個結(jié)點(diǎn)的編號是col，那么他的左孩子編號是col - 1
右孩子是 col + 1
然后我一下子開竅了.

然后利用兩個queue，一個存結(jié)點(diǎn)，一個存編號，兩者始終同步，再加上level order，解決了這個問題。

但是仔細(xì)看我代碼的最后部分。
因?yàn)樽詈蠓祷氐慕Y(jié)果，編號肯定是從小到大的，而hashmap返回的keyset并不能保證有序性。所以我先把所有的key放入一個數(shù)組，再排序，再從map取出對應(yīng)的list，速度收到了很大的影響。

然后我看了別人的代碼：
Their code:

public List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if(root == null) return res;
    
    Map<Integer, ArrayList<Integer>> map = new HashMap<>();
    Queue<TreeNode> q = new LinkedList<>();
    Queue<Integer> cols = new LinkedList<>();

    q.add(root); 
    cols.add(0);

    int min = 0, max = 0;
    while(!q.isEmpty()) {
        TreeNode node = q.poll();
        int col = cols.poll();
        if(!map.containsKey(col)) map.put(col, new ArrayList<Integer>());
        map.get(col).add(node.val);

        if(node.left != null) {
            q.add(node.left); 
            cols.add(col - 1);
            if(col <= min) min = col - 1;
        }
        if(node.right != null) {
            q.add(node.right);
            cols.add(col + 1);
            if(col >= max) max = col + 1;
        }
    }

    for(int i = min; i <= max; i++) {
        res.add(map.get(i));
    }

    return res;
}

仔細(xì)看他是怎么處理的？
他設(shè)置了一個min, 一個 max
因?yàn)槲覀冎溃@些編號最后肯定是從小到大，然后相鄰都是相差1的
所以如果我們有了min and max,就可以從小到大，從左往右把所有的list 按序拿出來。
一下子就快了好多。
實(shí)在是很巧妙。

reference:
https://discuss.leetcode.com/topic/31954/5ms-java-clean-solution/2

然后有些人沒想到這個好辦法，為了解決這個問題，他們不用HashMap,轉(zhuǎn)而用 TreeMap.
他的keySet 返回的是升序的set，所以就解決了這個問題。
但是相比于最簡單的方法， 效率還是受到了一定的影響。

馬上再研究下，
HashMap vs TreeMap

Anyway, Good luck, Richardo! -- 09/06/2016