Java 6ms AC solution with bfs+hashMap


  • 0
    W

    Solution is simple bfs+hashMap.

    public class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        HashMap<Integer,List<Integer>> map=new HashMap<Integer,List<Integer>>();
        List<List<Integer>> ret=new LinkedList<List<Integer>>();
        if(root==null) return ret;
        Queue<TreeNode> qNode=new LinkedList<TreeNode>();
        Queue<Integer> qCol=new LinkedList<Integer>();
        qNode.add(root);
        qCol.add(0);
        while(!qNode.isEmpty()){
            TreeNode n=qNode.poll();
            int col=qCol.poll();
            if(!map.containsKey(col))map.put(col,new LinkedList<Integer>());
            map.get(col).add(n.val);
            if(n.left!=null){
                qNode.add(n.left);
                qCol.add(col-1);
            }
            if(n.right!=null){
                qNode.add(n.right);
                qCol.add(col+1);
            }
        }
        int minCol=0; int maxCol=0;
        for(Integer col:map.keySet()){
            minCol=Math.min(minCol,col);
            maxCol=Math.max(maxCol,col);
        }
        for(int col=minCol;col<=maxCol;col++){
            ret.add(map.get(col));
        }
        return ret;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.