Binary Tree Vertical Order Traversal

lc 314

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.

这个题目就是root的level是0，然后左边孩子level － 1，右边孩子level＋ 1；然后用一个hashmap来存每个level的node值都有哪些。然后用bfslevel tranversal这个tree就可以了。一开始我为了记录level值，想要创建一个新的class，后来发现没有必要，再开一个level，同时存level值，这样每次取queue取node的时候，pop出来的也是level 值了。

这里我用了treemap，因为从小到达遍历结果。如果不让用treemap，可以在level trevasesal的时候记录下level的最大值和最小值然后for loop解决

o(n)解决 开了一个hashmap o（n）空间

/**
 * 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>> res = new ArrayList<List<Integer>>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        Queue<Integer> level = new LinkedList<Integer>();
        TreeMap<Integer, List<Integer>> map = new TreeMap<Integer, List<Integer>>();
        level.add(0);
        queue.add(root);
        List<Integer> list1 = new ArrayList<Integer>();
        list1.add(root.val);
        map.put(0, list1);
        while(! queue.isEmpty()){
            TreeNode cur = queue.poll();
            int l = level.poll();
            if(cur.left != null){
                level.add(l - 1);
                queue.add(cur.left);
                if(map.containsKey(l - 1)){
                    map.get(l - 1).add(cur.left.val);

                }else{
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(cur.left.val);
                    map.put(l - 1, list);
                }
            }
            if(cur.right != null){
                level.add(l + 1);
                queue.add(cur.right);
                if(map.containsKey(l + 1)){
                    map.get(l + 1).add(cur.right.val);
                }else{
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(cur.right.val);
                    map.put(l + 1, list);
                }
            }
        }

        for(Map.Entry me : map.entrySet()){
             res.add((List<Integer>)me.getValue());
        }


       /* Set set = map.entrySet();

      // Get an iterator
        Iterator i = set.iterator();

      // Display elements
        while(i.hasNext()) {
            Map.Entry me = (Map.Entry)i.next();
            res.add((List<Integer>)me.getValue());
      }*/
        return res;
    }
}