Java solution using Double Linked List


  • 0
    C
    public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            if(root == null){
                return result;
            }
            
            Set<TreeNode> visited = new HashSet<TreeNode>();
            visited.add(null);
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
            
            NodeList head = new NodeList();
            Map<TreeNode, NodeList> nodeListMap = new HashMap<TreeNode, NodeList>();
            nodeListMap.put(root, head);
            
            while(!queue.isEmpty()){
                TreeNode top = queue.poll();
                NodeList cur = nodeListMap.get(top);
                cur.nodes.add(top.val);
                
                if(visited.add(top.left)){
                    queue.offer(top.left);
                    if(cur.left == null){
                        cur.left = new NodeList();
                        cur.left.right = cur;
                        head = cur.left;
                    }
                    
                    nodeListMap.put(top.left, cur.left);
                }
    
                if(visited.add(top.right)){
                    queue.offer(top.right);
                    if(cur.right == null){
                        cur.right = new NodeList();
                        cur.right.left = cur;
                    }
                    nodeListMap.put(top.right, cur.right);
                }
            }            
            
            while(head != null){
                List<Integer> nodeCols = new ArrayList<Integer>();
                for(int val : head.nodes){
                    nodeCols.add(val);
                }
                result.add(nodeCols);
                head = head.right;
            }
            
            return result;
        }
        
        private static class NodeList{
            NodeList left;
            NodeList right;
            List<Integer> nodes = new ArrayList<Integer>();
        }
    

    Linked list can be replaces by using another queue to track the index, below is the modified above snippet

    public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            if(root == null){
                return result;
            }
            
            int minIdx = 0, maxIdx = 0;
            
            Set<TreeNode> visited = new HashSet<TreeNode>();
            visited.add(null);
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
            
            Queue<Integer> colQueue = new LinkedList<Integer>();
            colQueue.add(0);
            
            Map<Integer, List<Integer>> nodeListMap = new HashMap<Integer, List<Integer>>();
            nodeListMap.put(0, new ArrayList<Integer>());
            
            while(!queue.isEmpty()){
                TreeNode top = queue.poll();
                int idx = colQueue.poll();
                
                minIdx = Math.min(minIdx, idx);
                maxIdx = Math.max(maxIdx, idx);
                
                nodeListMap.get(idx).add(top.val);
                
                if(visited.add(top.left)){
                    queue.offer(top.left);
                    colQueue.offer(idx-1);
                    if(!nodeListMap.containsKey(idx - 1)){
                        nodeListMap.put(idx-1, new ArrayList<Integer>());
                    }
                }
    
                if(visited.add(top.right)){
                    queue.offer(top.right);
                    colQueue.offer(idx+1);
                    if(!nodeListMap.containsKey(idx + 1)){
                        nodeListMap.put(idx+1, new ArrayList<Integer>());
                    }
                }
            }            
            
            for(int i=minIdx; i<=maxIdx; i++){
                result.add(nodeListMap.get(i));
            }
            
            return result;
        }
    
    

Log in to reply
 

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