leetcode987. 二叉树的垂序遍历
给定二叉树，按垂序遍历返回其结点值。
对位于 (X, Y) 的每个结点而言，其左右子结点分别位于 (X-1, Y-1) 和 (X+1, Y-1)。
把一条垂线从 X = -infinity 移动到 X = +infinity ，每当该垂线与结点接触时，我们按从上到下的顺序报告结点的值（ Y 坐标递减）。
如果两个结点位置相同，则首先报告的结点值较小。
按 X 坐标顺序返回非空报告的列表。每个报告都有一个结点值列表。
示例 1：
输入：[3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]
解释：
在不丧失其普遍性的情况下，我们可以假设根结点位于 (0, 0)：
然后，值为 9 的结点出现在 (-1, -1)；
值为 3 和 15 的两个结点分别出现在 (0, 0) 和 (0, -2)；
值为 20 的结点出现在 (1, -1)；
值为 7 的结点出现在 (2, -2)。
示例 2：
输入：[1,2,3,4,5,6,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
根据给定的方案，值为 5 和 6 的两个结点出现在同一位置。
然而，在报告 “[1,5,6]” 中，结点值 5 排在前面，因为 5 小于 6。
提示：
树的结点数介于 1 和 1000 之间。
每个结点值介于 0 和 1000 之间。
我的思路
创建一个对象用来存储节点和对应的x，y坐标，先遍历一遍树，把所有的节点xy坐标都求出来，然后放到list里面排序，这样排好序的list再拆成最终结果就简单了。3ms。
这里对comparator的理解：
return -1，代表return false，我不想交换当前的两个值。
return 1，代表true，我想交换当前的两个值。
先对x升序排列，再对y降序排列，最后排列val。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| class Solution {
public class node{
int x;
int y;
int val;
public node(int val,int x,int y){
this.val=val;
this.x=x;
this.y=y;
}
}
public List<List<Integer>> verticalTraversal(TreeNode root) {
traverse(root,0,0);
Collections.sort(list, new Comparator<node>(){
@Override
public int compare(node o1, node o2) {
int a=o1.x-o2.x;
if(a>0){
return 1;
}else if(a<0){
return -1;
}else{
a=o1.y-o2.y;
if(a>0)return -1;
else if(a<0)return 1;
else {
a=o2.val-o1.val;
if(a>0)return -1;
else if(a<0)return 1;
else return 0;
}
}
}
});
LinkedList<Integer>res=null;
int prev=1;
for(node n :list){
int now=n.x;
if(prev!=now){
if(res!=null)
ans.add(res);
res=new LinkedList<>();
prev=now;
}
res.add(n.val);
}
ans.add(res);
return ans;
}
public LinkedList<List<Integer>>ans=new LinkedList<>();
public LinkedList<node>list=new LinkedList<>();
public void traverse(TreeNode root,int x,int y){
if(root==null)return;
list.add(new node(root.val,x,y));
traverse(root.left,x-1,y-1);
traverse(root.right,x+1,y-1);
}
}
|
leetcode 34/100