英文:
Problem with elements at same level with same vertical height in Vertical Order Traversal of a Binary Tree
问题
Here's the translated pseudocode:
- 创建一个类来存储节点和其水平高度
- 使用BFS，创建一个队列并插入水平高度为0的第一个节点
- 从队列中弹出元素，如果水平高度在映射中不存在，则创建一个条目
- 获取水平高度的ArrayList并将节点的值添加到其中
- 检查左子节点和右子节点，如果它们不为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;
}
}
请注意，这是代码的翻译部分，不包括输入和问题的内容。
英文:
Pseudocode
-
Created a class that will hold the node and its horizontal height
-
Using BFS, so create a queue and inserted the first node having a horizontal height of 0
-
Popped the element from the queue, if the horizontal height doesn't exist in the map then created an entry for it
-
get the ArrayList of horizontal height and add the value of the node to it
-
check for the left and right child, if they are not null then add them to the queue
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
Input:
[0,2,1,3,null,null,null,4,5,null,7,6,null,10,8,11,9]
答案1
得分: 0
Here's the translated content:
首先，您可能在谈论水平高度，而不是您的输出所示的垂直高度。您得到的输出似乎是正确的，因为在进行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());
英文:
First of all you are probably talking about horizontal height not vertical height as your output suggest. Output you got seems to be correct since when making BFS traversal you are first looking on the left element then the right from up to bottom independently on horizontal heights. Left node of the tree level will always be processed sooner (therefore also its child will be sooner added to the queue) so at level 3 (from up to bottom indexing from 0) node with value 7 will be sooner added to the queue for processing then node with value 6. Therefore output seems to be correct in my eyes, can you tell us why your are expecting different output ?
According to this sentence in your task link (https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/):
"If two nodes have the same position, then the value of the node that is reported first is the value that is smaller."
It seems that you need to sort your sublists inside resulting list. You can do that with following code:
sortedResult = resultList.stream()
.map(list -> list.stream().sorted().collect(Collectors.toList()))
.collect(Collectors.toList());
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论