Любая идея, почему Collections.sort () не работает в приведенной ниже программе?

Question

Я пытаюсь решить вопрос о Leetcode, который связан с вертикальным обходом двоичного дерева, и я написал следующий код. Здесь Collections.sort () не работает, и я не могу понять, почему. нужны некоторые указатели для исправления этого кода /

class Solution {
    Map<Integer,List<Integer>>map = new TreeMap<>();
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> verticalTraversal(TreeNode root)  {
        if(root == null)
            return null;
        rec(0,root);
        for(Integer i : map.keySet())
        {
            result.add((map.get(i)));
        }
        return result;

    }
    public void rec(int pos, TreeNode node)
    {
        if(node == null)
            return;
        List<Integer>list = map.get(pos);
        if(list == null)
        {
            list = new ArrayList<Integer>();
            list.add(node.val);
            Collections.sort(list);
            map.put(pos,list);
        }
        else
            list.add(node.val);
        rec(pos-1,node.left);
        rec(pos+1,node.right);
    }
}

Входной сигнал: [0,8,1, NULL, NULL, 3,2, NULL, 4,5, NULL, NULL, 7,6]

Ожидается: [[8], [0,3,6], [1,4,5], [2,7]] Фактически: [[8], [0,3,6], [1,4,5], [7,2]]

Answer 1

if (list == null) {
            list = new ArrayList<Integer>();
            list.add(node.val);
            Collections.sort(list);
            map.put(pos, list);
        }

Пожалуйста, попробуйте отсортировать элементы после добавления всех элементов на карте.

Answer 2

Вы сортируете внутренние списки только один раз, когда создаете их.Было бы более разумно отсортировать их после добавления всех элементов.

Удалите текущее

Collections.sort(list);

и добавьте

for (List<Integer> list : map.values()) {
    Collections.sort(list);
}

после того, как вы добавите все числако всем List s.

Если вам нужно отсортировать List после каждого добавленного элемента (что было бы менее эффективно), вам нужно сортировать List каждый раз, когда вы добавляетеэлемент.

    if(list == null)
    {
        list = new ArrayList<Integer>();
        list.add(node.val);
        Collections.sort(list);
        map.put(pos,list);
    }
    else
        list.add(node.val);

станет

    if(list == null)
    {
        list = new ArrayList<Integer>();
        list.add(node.val); // no need to sort a List with a single element
        map.put(pos,list);
    }
    else {
        list.add(node.val);
        Collections.sort(list);
    }