Explanation with Java code


  • 0
    L

    The key pattern in this algorithm is to that a left child is one col left to the parent and the right child is one col right to the parent. Also, if you look through the examples, BFS is the way to go to maintain the sequence of traversal. Here is the Java code:

        public List<List<Integer>> verticalOrder(TreeNode root) {
            if(root==null) {
                return Collections.emptyList();
            }
            
            
            Map<Integer,List<Integer>> map = new TreeMap<>();
            Queue<Wrapper> queue = new LinkedList<>();
            queue.add(new Wrapper(root,0));
            while(!queue.isEmpty()) {
                Wrapper w = queue.poll();
                List<Integer> l = map.get(w.count);
                if(l==null) {
                    l = new ArrayList<>();
                    map.put(w.count,l);                    
                }
                l.add(w.node.val);
                
                if(w.node.left!=null) {
                    queue.add(new Wrapper(w.node.left,w.count-1));
                }
                if(w.node.right!=null) {
                    queue.add(new Wrapper(w.node.right,w.count+1));
                }
            }
            
            List<List<Integer>> list = new ArrayList<>();
            for(List<Integer> l : map.values()) {
                list.add(l);
            }
            return list;        
        }
        
        private class Wrapper {
            private TreeNode node;
            private int count;
            Wrapper(TreeNode node, int count) {
                this.node = node;
                this.count = count;
            }
        }
    

Log in to reply
 

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