二叉树的垂直顺序遍历中具有相同垂直高度的同一级别的元素的问题

Question

伪代码

创建了一个 class 来保存节点及其水平高度
使用BFS，所以创建一个队列并插入第一个水平高度为0的节点
从队列中弹出元素，如果地图中不存在水平高度则为其创建一个条目
获取水平高度的ArrayList并将节点的值添加到其中

检查左侧和右侧child，如果它们不为空则将它们添加到队列

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,null,null,null,4,5,null,7,6,null,10,8,11,9]

Answer 1

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

根据你任务中的这句话link (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());

二叉树的垂直顺序遍历中具有相同垂直高度的同一级别的元素的问题

Problem with elements at same level with same vertical height in Vertical Order Traversal of a Binary Tree

java

binary-tree

breadth-first-search

tree-traversal