Easy to understand Java Solution using level-order-traversal


  • 0
    public class Solution {
        
        class Tuple {
            int idx;
            TreeNode node;
            Tuple(int idx, TreeNode node) { 
                this.idx = idx; 
                this.node = node; 
            }
        }
        
        public void addToHtbl(Map<Integer,List<Integer>> htbl, int idx, int val) {
            if(htbl.containsKey(idx))
                htbl.get(idx).add(val);
            else {
                List<Integer> l = new ArrayList<Integer>();
                l.add(val);
                htbl.put(idx,l);
            }
        }
     
        public void levelOrderTrav(TreeNode root, Map<Integer,List<Integer>> htbl) {
            Queue<Tuple> queue = new LinkedList<Tuple>();
            queue.offer(new Tuple(0, root));
            while(!queue.isEmpty()) {
                Tuple t = queue.poll();
                int idx = t.idx;
                TreeNode node = t.node;
                addToHtbl(htbl, idx, node.val);
                if(node.left != null)
                    queue.offer(new Tuple(idx-1, node.left));
                if(node.right != null)
                    queue.offer(new Tuple(idx+1, node.right));
            }
        }
        
        public List<List<Integer>> verticalOrder(TreeNode root) {
            List l = new ArrayList<List>();
            if(root==null)
                return l;
            Map<Integer,List<Integer>> htbl = new HashMap<Integer,List<Integer>>();
            levelOrderTrav(root, htbl);
            
            for(int i=0; i<htbl.size(); i++)
                l.add(null);
            
            int min = 0;
            for(Map.Entry<Integer,List<Integer>> entry : htbl.entrySet())
                if(entry.getKey() < min)
                    min = entry.getKey();
                    
            for(Map.Entry<Integer,List<Integer>> entry : htbl.entrySet())
                l.set(entry.getKey()-min, entry.getValue());
            
            return l;
        }
    }

  • 0
    H

    too slow. How to improve?


Log in to reply
 

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