Java with HashMap, O(n) time and space complexity


  • 0
    R
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();
        if (root == null) {
            return result;
        }
        
        Map<Integer, List<Integer>> colMap = new HashMap<>();
        Map<TreeNode, Integer> treeColMap = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        
        queue.offer(root);
        treeColMap.put(root, 0);
        
        while (!queue.isEmpty()) {
            TreeNode currentNode = queue.poll();
            
            int currentCol = treeColMap.get(currentNode);
            
            min = Math.min(min, currentCol);
            max = Math.max(max, currentCol);
            
            if (!colMap.containsKey(currentCol)) {
                List<Integer> list = new LinkedList<>();
                colMap.put(currentCol, list);
            }
            
            colMap.get(currentCol).add(currentNode.val);
            
            if (currentNode.left != null) {
                queue.offer(currentNode.left);
                treeColMap.put(currentNode.left, currentCol - 1);
            }
            
            if (currentNode.right != null) {
                queue.offer(currentNode.right);
                treeColMap.put(currentNode.right, currentCol + 1);
            }
        }
        
        for (int i = min; i <= max; i++) {
            if (colMap.containsKey(i)) {
                result.add(colMap.get(i));
            }
        }
        
        return result;
    }
    

    }


Log in to reply
 

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