2024.2.13力扣每日一题——二叉树的垂序遍历

题目来源

力扣每日一题；题序：987

我的题解

方法一 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);
    }
}
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

// 第二个版本  使用了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);
    }
}
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

方法二 官方题解（自定义排序） 数组实现

来源：官方题解
从根节点开始，对整棵树进行一次遍历，在遍历的过程中使用数组 nodes 记录下每个节点的行号 row，列号 col 以及值 value。在遍历完成后，我们按照 col为第一关键字升序，row为第二关键字升序，value 为第三关键字升序，对所有的节点进行排序即可。
在排序完成后，我们还需要按照题目要求，将同一列的所有节点放入同一个数组中。因此，我们可以对 nodes 进行一次遍历，并在遍历的过程中记录上一个节点的列号 lastcol。如果当前遍历到的节点的列号 col与 lastcol相等，则将该节点放入与上一个节点相同的数组中，否则放入不同的数组中。

时间复杂度：O(nlogn)，其中 n 是树中的节点个数。我们需要 O(n) 的时间对整棵树进行一次遍历（例如代码中的深度优先搜索），随后需要 O(nlog⁡n) 的时间对数组 nodes进行排序，以及 O(n)的时间对数组 nodes 进行遍历得到最终的答案。由于 O(nlog⁡n) 在渐近意义下大于 O(n)，所以算法的总时间复杂度为 O(nlog⁡n)。
空间复杂度：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);
    }
}

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

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈