My Java solution (preorder traversal + TreeMap)


  • 0
    V
    class LevelValue implements Comparable<LevelValue> {
        int level;
        int value;
        public LevelValue(int level, int value) {
            this.level = level;
            this.value = value;
        }
    
        @Override
        public int compareTo(LevelValue o) {
            return this.level-o.level;
        }
    }
    
    public List<List<Integer>> verticalOrder(TreeNode root) {
        Map<Integer, List<LevelValue>> map = new TreeMap<>();
        helper(root, 0, 0, map);
        List<List<Integer>> result = new ArrayList<>();
        for (Integer key: map.keySet()) {
            List<LevelValue> valueList = map.get(key);
            Collections.sort(valueList);
            List<Integer> intList = new ArrayList<>();
            for (LevelValue v:valueList) {
                intList.add(v.value);
            }
            result.add(intList);
        }
        return result;
    }
    
    public void helper(TreeNode root, int key, int level, Map<Integer, List<LevelValue>> map) {
        if (root == null) return;
        if (!map.containsKey(key)) map.put(key, new ArrayList<>());
        List<LevelValue> theList = map.get(key);
        theList.add(new LevelValue(level, root.val));
        helper(root.left, key-1, level+1, map);
        helper(root.right, key+1, level+1, map);
    }

Log in to reply
 

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