2024.2.13
题目来源
我的题解
方法一 TreeMap+深度优先遍历
在递归形式的前、中、后序遍历中任选一种进行遍历，并在遍历过程中记录元素的行和列，并利用TreeMap可以自定义排序的特点将其按列升序再按行升序排序。最后根据遍历TreeMap来得到最终的结果。
时间复杂度：分析不明白 打扰了
空间复杂度：分析不明白 打扰了
//第一个版本 未用TreeMap
class Solution {
HashMap<String,List<Integer>> map=new HashMap<>();
//记录最小列和最大列
int min=Integer.MAX_VALUE;
int max=Integer.MIN_VALUE;
public List<List<Integer>> verticalTraversal(TreeNode root) {
List<List<Integer>> res=new ArrayList<>();
if(root==null)
return res;
preOrder(root,0,0);
// String s=map.firstKey();
List<Map.Entry<String, List<Integer>>> list = new ArrayList<>(map.entrySet());
//排序
Collections.sort(list, (o1, o2) -> {
String a=o1.getKey();
String b=o2.getKey();
int col1=Integer.parseInt(a.substring(0,a.lastIndexOf("split")));
int row1=Integer.parseInt(a.substring(a.lastIndexOf("split")+5));
int col2=Integer.parseInt(b.substring(0,b.lastIndexOf("split")));
int row2=Integer.parseInt(b.substring(b.lastIndexOf("split")+5));
if(col1==col2){
return row1-row2;
}else{
return col1-col2;
}
});
//初始化结果TreeMap
TreeMap<Integer,List<Integer>> map1=new TreeMap<>();
for(int i=min;i<=max;i++) {
map1.put(i, new ArrayList<>());
}
for(Map.Entry<String,List<Integer>> entry:list){
String key=entry.getKey();
//得到所在的列
int colT=Integer.parseInt(key.substring(0,key.lastIndexOf("split")));
List<Integer> l=map1.get(colT);
List<Integer> t=entry.getValue();
//同行同列的需要升序排序
t.sort((a,b)->a-b);
l.addAll(t);
//将列相同的放到同一个列表
map1.put(colT,l);
}
for(Map.Entry<Integer,List<Integer>> entry:map1.entrySet()){
res.add(entry.getValue());
}
return res;
}
public void preOrder(TreeNode root,int col,int row){
if(root==null)
return;
min=Math.min(min,col);
max=Math.max(max,col);
String key=col+"split"+row;
List<Integer> list=map.getOrDefault(key,new ArrayList<>());
list.add(root.val);
map.put(key,list);
preOrder(root.left,col-1,row+1);
preOrder(root.right,col+1,row+1);
}
}
// 第二个版本 使用了TreeMap
class Solution {
//定义TreeMap的排序
TreeMap<String, List<Integer>> map=new TreeMap<>((a,b) -> {
int col1=Integer.parseInt(a.substring(0,a.lastIndexOf("split")));
int row1=Integer.parseInt(a.substring(a.lastIndexOf("split")+5));
int col2=Integer.parseInt(b.substring(0,b.lastIndexOf("split")));
int row2=Integer.parseInt(b.substring(b.lastIndexOf("split")+5));
if(col1==col2){
return row1-row2;
}else{
return col1-col2;
}
});
public List<List<Integer>> verticalTraversal(TreeNode root) {
List<List<Integer>> res=new ArrayList<>();
if(root==null)
return res;
preOrder(root,0,0);
//由于按照列升序排序了，第一个key就是最小的列
String s=map.firstKey();
int col=Integer.parseInt(s.substring(0,s.lastIndexOf("split")));
List<Integer> l=new ArrayList<>();
for(Map.Entry<String,List<Integer>> entry:map.entrySet()){
String key=entry.getKey();
int colT=Integer.parseInt(key.substring(0,key.lastIndexOf("split")));
//当列改变，表示当前列的所有行已经遍历完，可以将其记录到结果中
if(colT!=col){
res.add(new ArrayList<>(l));
l=new ArrayList<>();
col=colT;
}
List<Integer> t=entry.getValue();
t.sort((a,b)->a-b);
l.addAll(t);
}
//注意最后一个列
res.add(l);
return res;
}
public void preOrder(TreeNode root,int col,int row){
if(root==null)
return;
min=Math.min(min,col);
max=Math.max(max,col);
String key=col+"split"+row;
List<Integer> list=map.getOrDefault(key,new ArrayList<>());
list.add(root.val);
map.put(key,list);
preOrder(root.left,col-1,row+1);
preOrder(root.right,col+1,row+1);
}
}
方法二 官方题解（自定义排序） 数组实现
来源：官方题解
从根节点开始，对整棵树进行一次遍历，在遍历的过程中使用数组 nodes 记录下每个节点的行号 row，列号 col 以及值 value。在遍历完成后，我们按照 col为第一关键字升序，row为第二关键字升序，value 为第三关键字升序，对所有的节点进行排序即可。
在排序完成后，我们还需要按照题目要求，将同一列的所有节点放入同一个数组中。因此，我们可以对 nodes 进行一次遍历，并在遍历的过程中记录上一个节点的列号 lastcol。如果当前遍历到的节点的列号 col与 lastcol相等，则将该节点放入与上一个节点相同的数组中，否则放入不同的数组中。
时间复杂度：O(nlogn)，其中 n 是树中的节点个数。我们需要 O(n) 的时间对整棵树进行一次遍历（例如代码中的深度优先搜索），随后需要 O(nlogn) 的时间对数组 nodes进行排序，以及 O(n)的时间对数组 nodes 进行遍历得到最终的答案。由于 O(nlogn) 在渐近意义下大于 O(n)，所以算法的总时间复杂度为 O(nlogn)。
空间复杂度：O(n)
class Solution {
public List<List<Integer>> verticalTraversal(TreeNode root) {
List<int[]> nodes = new ArrayList<int[]>();
dfs(root, 0, 0, nodes);
Collections.sort(nodes, new Comparator<int[]>() {
public int compare(int[] tuple1, int[] tuple2) {
if (tuple1[0] != tuple2[0]) {
return tuple1[0] - tuple2[0];
} else if (tuple1[1] != tuple2[1]) {
return tuple1[1] - tuple2[1];
} else {
return tuple1[2] - tuple2[2];
}
}
});
List<List<Integer>> ans = new ArrayList<List<Integer>>();
int size = 0;
int lastcol = Integer.MIN_VALUE;
for (int[] tuple : nodes) {
int col = tuple[0], row = tuple[1], value = tuple[2];
if (col != lastcol) {
lastcol = col;
ans.add(new ArrayList<Integer>());
size++;
}
ans.get(size - 1).add(value);
}
return ans;
}
public void dfs(TreeNode node, int row, int col, List<int[]> nodes) {
if (node == null) {
return;
}
nodes.add(new int[]{col, row, node.val});
dfs(node.left, row + 1, col - 1, nodes);
dfs(node.right, row + 1, col + 1, nodes);
}
}
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈
标签：2024.2,return,int,垂序,二叉树,new,root,col,row From： https://blog.csdn.net/weixin_42075274/article/details/137218855