在二叉树的垂直顺序遍历中，元素处于同一级别且垂直高度相同的java问题

Question

伪代码

1. 创建了一个类，该类将保存节点及其水平高度

2. 使用BFS，因此创建一个队列并插入第一个水平高度为0的节点

3. 从队列中弹出元素，如果水平高度在映射中不存在，则为其创建一个条目

4. 获取水平高度的ArrayList并将节点的值添加到其中

5. 检查左侧和右侧子级，如果它们不为null，则将它们添加到队列中

   class Solution {
   
     class Node{
       TreeNode key;
       int h;
       Node(TreeNode key,int h){
           this.key=key;
           this.h=h;
         }
      }
   
   public List<List<Integer>> verticalTraversal(TreeNode root) {
       if(root==null)
           return null;
       TreeMap<Integer, ArrayList<Integer>> map = new TreeMap<>();
       Queue<Node> q=new LinkedList<>();
       q.add(new Node(root,0));
   
       while(!q.isEmpty()){
           Node tmp=q.poll();
           if(!map.containsKey(tmp.h))
               map.put(tmp.h,new ArrayList<Integer>());
           map.get(tmp.h).add(tmp.key.val);           
           if(tmp.key.left!=null)
               q.add(new Node(tmp.key.left,tmp.h-1));
           if(tmp.key.right!=null)
               q.add(new Node(tmp.key.right,tmp.h+1));
       }
   
       List<List<Integer>> ans=new ArrayList<>();
       for(ArrayList<Integer> al:map.values()){
           ans.add(al);
       }
       return ans;
   }
   

   }

Problem Failing for input

输入： [0,2,1,3，空，空，空，4,5，空，7,6，空，10,8,11,9]

Answer 1

首先，您可能正在讨论水平高度，而不是输出所建议的垂直高度。您得到的输出似乎是正确的，因为在进行BFS遍历时，您首先查看左侧元素，然后在水平高度上从上到下独立查看右侧元素。树级别的左侧节点总是会被更快地处理（因此其子节点也会更快地添加到队列中），因此在级别3（从0开始从上到下索引），值为7的节点会更快地添加到队列中进行处理，然后是值为6的节点。因此，在我看来，输出似乎是正确的，你能告诉我们为什么你期望不同的输出吗

根据任务链接（https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/）中的这句话：
如果两个节点的位置相同，则首先报告的节点的值较小

似乎需要在结果列表中对子列表进行排序。可以使用以下代码执行此操作：

sortedResult = resultList.stream()
    .map(list -> list.stream().sorted().collect(Collectors.toList()))
    .collect(Collectors.toList());