算法

【新手006】对数器、优先级队列、二叉树

Posted by Hilda on September 7, 2025

1.对数器

implements Comparator的类，需要实现compare(T o1, T o2)方法，这个方法返回一个int类型的值，int是负数时，返回前面那个对象，否则返回后面那个对象，即：

  • 如果返回值是负数：这意味着 o1 小于 o2。在排序时，o1 会排在 o2 前面。
  • 如果返回值是正数：这意味着 o1 大于 o2。在排序时，o1 会排在 o2 后面。
  • 如果返回值是零：这意味着 o1 等于 o2。它们的相对顺序不会改变。

例如下面的Student类，有name，id，age三个属性，现在按照age属性进行升序排序：

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

public class Student {
    private String name;
    private int id;
    private int age;

    public String getName() {
        return name;
    }

    public int getId() {
        return id;
    }

    public int getAge() {
        return age;
    }

    public Student(String name, int id, int age) {
        this.name = name;
        this.id = id;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", id=" + id +
                ", age=" + age +
                '}';
    }
}
class ageComparator implements Comparator<Student> {

    @Override
    public int compare(Student o1, Student o2) {
        return o1.getAge() - o2.getAge();
    }
}

测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class  TestAge{

    public static void printStudents(Student[] students) {
        for (Student student : students) {
            System.out.println(student);
        }
    }
    public static void main(String[] args) {
        Student s1 = new Student("张三", 9, 10);
        Student s2 = new Student("里斯", 0, 28);
        Student s3 = new Student("万物", 7, 23);
        Student s4 = new Student("糟熘", 2, 9);

        Student[] students = {s1, s2, s3, s4};
        Arrays.sort(students, new ageComparator());
        printStudents(students);
    }
}

如果容器不是数组，而是一个ArrayList，在调用sort方法时，传入即可：arrayList.sort(new ageComparator());

1
2
3
4
5
6
7
8
9
10

ArrayList<Student> arrayList = new ArrayList<>();
arrayList.add(s1);
arrayList.add(s2);
arrayList.add(s3);
arrayList.add(s4);

arrayList.sort(new ageComparator());
for (Student student :arrayList) {
    System.out.println(student);
}

2.优先级队列/小根堆

java内置的优先级队列PriorityQueue其实就是小根堆，每次你从队列中取出元素时，它总是返回优先级最高的那个元素。（Integer的话就是返回最小，小根堆）

常用方法：

  • 添加元素 (add() 或 offer())
  • 获取并移除堆顶元素 (poll())
  • 获取堆顶元素但不移除 (peek())

另外，PriorityQueue完全支持存储重复的元素。

优先级队列时间复杂度是O(logn)

比如：

1
2
3
4
5
6

PriorityQueue<Integer> heap = new PriorityQueue<>();
heap.add(10);
heap.add(1);
heap.add(11);
heap.add(5);
System.out.println(heap.peek()); // 返回1

如果你需要一个大根堆（根节点最大），可以通过给 PriorityQueue 传入一个自定义比较器来实现。

比如：

1
2

PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); // 降序
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new MyComparator()); // 自定义

TreeMap和TreeSet同理。

补一个简单的知识点：String如何比较？—-字典序

逐个字符比较：从两个字符串的第一个字符开始比较。

第一个不同字符决定顺序：（基于字母顺序）

  • 如果第一个不同字符在字母表中的位置靠前，则整个字符串靠前。
  • 如果第一个不同字符在字母表中的位置靠后，则整个字符串靠后。

短字符串优先：如果一个字符串是另一个字符串的前缀，那么较短的那个字符串排在前面。

在Java中，String 类的 compareTo() 方法就是用来执行字典顺序比较的。如果你想忽略大小写，则可以使用 compareToIgnoreCase() 方法。

3.力扣23-合并k个升序链表

力扣：https://leetcode.cn/problems/merge-k-sorted-lists/

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0 ) return null;
        if (lists.length == 1) return lists[0];
        // 小根堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>((o1, o2)->o1.val-o2.val);
        for (ListNode l:lists) {
            if (l != null) {
                heap.add(l);
            }
        }
        ListNode head = heap.poll();
        if (head != null && head.next != null) heap.add(head.next);
        ListNode cur = head;
        while (!heap.isEmpty()) {
            ListNode poll = heap.poll();
            if (poll != null && poll.next != null) heap.add(poll.next);
            cur.next = poll;
            cur = cur.next;
        }
        return head;

    }
}

估计时间复杂度：假设一共有k个链表，节点总数是n，

那么小根堆的大小最大是k，小根堆的调整O(logk)，每个节点进来/出去，一共发生n次，所以时间复杂度O(nlogk)

4.递归序的实质

递归序，又称为遍历序或欧拉序（Euler tour），其本质是将一棵树的遍历过程，转化为一个一维序列（数组）。

简单来说，它记录了在树的深度优先遍历（DFS）过程中，每个节点被访问的完整路径。

从根节点出发，总是优先向左走。当沿着树的边缘移动时，每当经过一个节点，无论是第一次、第二次还是最后一次，你都把它记录下来。

这个“经过并记录”的过程，就是生成递归序的实质。

具体来说，当一个节点 x 被访问时，有三种情况：

  1. 第一次访问 (pre-order 阶段)：当你从父节点来到 x 的时候，这是你第一次见到它。
  2. 从左子树返回 (in-order 阶段)：当你走完 x 的左子树，回到 x 准备进入右子树时。
  3. 从右子树返回 (post-order 阶段)：当你走完 x 的右子树，准备从 x 返回到父节点时。

递归序就是把这三种情况下的访问都记录下来。

递归序将复杂的树结构问题，降维成了一维数组上的子序列问题，使得原本需要多次遍历才能解决的问题，现在只需要对一个数组进行简单的查找和计算即可。

1
2
3
4
5
6
7
8
9
10

public static void f(Node head) {
  if (head == null) {
    return;
  }
  // 1
  f(head.left);
  // 2
  f(head.right);
  // 3
}

5.判断是否为相等的树

力扣：https://leetcode.cn/problems/same-tree/description/

牛客：（填函数风格）https://www.nowcoder.com/practice/5a3b2cf4211249c89d6ced7987aeb775

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // （p == null 且q != null） 或者（p ！= null 且q == null）
        if (p == null ^ q == null) { 
            return false;
        }
        if (p == null && q == null) {
            return true;
        }
        return (p.val == q.val) && (isSameTree(p.left, q.left)) && (isSameTree(p.right, q.right));
    }
}

6.判断一棵树是否是镜面树(对称二叉树)

力扣：https://leetcode.cn/problems/symmetric-tree

牛客：填函数风格：https://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb?tpId=0

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirrors(root, root);
    }
    public boolean isMirrors(TreeNode r1, TreeNode r2) {
        if (r1 == null ^ r2 == null) {
            return false;
        }
        if (r1 == null && r2 == null) {
            return true;
        }
        return (r1.val == r2.val) && (isMirrors(r1.left, r2.right)) && (isMirrors(r1.right, r2.left));
    }
}

7.返回一棵树的最大深度

力扣：https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

牛客（填函数风格）：https://www.nowcoder.com/practice/435fb86331474282a3499955f0a41e8b

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

8.从前序与中序遍历序列构造二叉树

力扣105: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length != inorder.length) return null;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0;i < inorder.length;i++){
            map.put(inorder[i], i);
        }
        return f(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map);
    }
    public TreeNode f(int[] preorder,int L1, int R1, int[] inorder, int L2, int R2, HashMap<Integer, Integer> map) {
        if (L1 > R1) {
            return null;
        }
        TreeNode head = new TreeNode(preorder[L1]);
        if (L1 == R1) {
            return head;
        }
        // 找头
        int find = map.get(head.val);
        head.left = f(preorder,L1 + 1 , L1 +find - L2,inorder, L2, find - 1, map);
        head.right = f(preorder, L1 +find - L2 + 1, R1, inorder, find + 1, R2, map);
        return head;
    }
}

时间复杂度分析

  • 哈希表构建：for (int i = 0; i < inorder.length; i++) 循环需要 O(N) 的时间，其中 N 是节点总数。
  • 递归过程：
    • f 函数被调用的次数等于树的节点数，即 N。
    • 在每次 f 函数调用中，主要操作是哈希表查找（map.get()），其时间复杂度是 O(1)。
    • 因此，递归过程的总时间复杂度为 O(N * 1) = O(N)。
  • 总时间复杂度：O(N)（构建哈希表）+ O(N)（递归） = O(N)。

9.从中序和后序遍历构造二叉树

类似题目：

从中序和后序遍历构造二叉树（牛客，填函数风格）：https://www.nowcoder.com/practice/b0d07d0edc7f495696aecd265d5ef1b9

同理，从中序和后序遍历序列构造二叉树的解法页类似，但是特别注意下面这2行下标的问题，很容易错，建议带入具体的例子。测试链接：

1
2

root.left = g(inorder, L1, find - 1, postorder, L2, L2 + find - L1 - 1, map);
root.right = g(inorder, find + 1, R1, postorder, L2 + find - L1, R2 - 1, map);

完整解法：

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

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param inorder int整型一维数组 
     * @param postorder int整型一维数组 
     * @return TreeNode类
     */
    public TreeNode buildTree (int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length != postorder.length) {
            return null;
        }
        // 准备一个HashMap  中序快速索引
        HashMap<Integer, Integer> inMap = new HashMap<>();
        for (int i = 0;i < inorder.length;i++) {
            inMap.put(inorder[i], i);
        }
        return g(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, inMap);
    }

    public TreeNode g(int[] inorder,int L1, int R1, int[] postorder, int L2, int R2, HashMap<Integer, Integer> map) {
        if (L2 > R2) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[R2]);
        if (L2 == R2) {
            return root;
        }
        // 找头
        int find = map.get(root.val);
        root.left = g(inorder, L1, find - 1, postorder, L2, L2 + find - L1 - 1, map);
        root.right = g(inorder, find + 1, R1, postorder, L2 + find - L1, R2 - 1, map);
        return root;
    }
}

类似的，时间复杂度也是O(N)

分析如下：

  • 哈希表构建：O(N)，其中 N 是节点总数。
  • 递归过程：
    • g 函数被调用的次数等于树的节点数，即 N。
    • 在每次调用中，哈希表查找的时间复杂度是 O(1)。
    • 因此，递归过程的总时间复杂度为 O(N * 1) = O(N)。
  • 总时间复杂度：O(N)（构建哈希表）+ O(N)（递归） = O(N)。
CATALOG
    FEATURED TAGS
    书籍阅读 算法 人工智能AI基础 python基础 力扣 numpy pandas 机器学习-吴恩达 机器学习算法 matplotlib spring6 Java基础 java集合 ollama工具 python爬虫
    FRIENDS