新手入门篇-优先级队列、二叉树 2021-06-22 111 阅读3分钟专栏：数据结构与算法-灵析社区

优先级队列

PriorityQueue的使用，默认小顶堆。

基本的应用场景

public class Code01_ShowComparator {

    public static class Student {
        public String name;
        public int id;
        public int 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 +
                    '}';
        }
    }

    public static class IdComparator implements Comparator<Student> {

        @Override
        public int compare(Student s1, Student s2) {
            return Integer.compare(s1.id, s2.id);
        }
    }

    public static void main(String[] args) {
        Student s1 = new Student("张三", 5, 27);
        Student s2 = new Student("李四", 1, 17);
        Student s3 = new Student("王五", 4, 29);
        Student s4 = new Student("赵六", 3, 9);
        Student s5 = new Student("左七", 2, 34);
        PriorityQueue<Student> heap = new PriorityQueue<>(new IdComparator());
        heap.add(s1);
        heap.add(s2);
        heap.add(s3);
        heap.add(s4);
        heap.add(s5);
        while (!heap.isEmpty()) {
            System.out.println(heap.poll());
        }
    }
}

合并多个有序链表

举例：

1->2->4->6

3->5->7

2->8->9

合并后链表为：1->2->2->3->4->5->6->7->8->9

思路：首先把所有有序链表按照自定义比较器规则加入优先级队列中，则所有链表的头节点默认就排好序了，形成小顶堆。然后取出头节点，把头的下一个节点再次入队，周而复始。

public class Code02_MergeKSortedLists {

    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static class ListNodeComparator implements Comparator<ListNode> {

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

    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }
        PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator());
        // 把所有链表都加入优先级队列中，按照比较器规则，添加完后自动形成小顶堆
        for (int i = 0; i < lists.length; i++) {
            heap.add(lists[i]);
        }
        if (heap.isEmpty()) {
            return null;
        }
        ListNode head = heap.poll();
        ListNode pre = head;
        if (pre.next != null) {
            heap.add(pre.next);
        }
        while (!heap.isEmpty()) {
            ListNode cur = heap.poll();
            pre.next = cur;
            pre = cur;
            if (cur.next != null) {
                heap.add(cur.next);
            }
        }
        return head;
    }
}

二叉树

二叉树的遍历

递归遍历

思路：

前序：头、左、右
中序：左、头、右
后序：左、右、头

public class Code03_TraversalBinaryTree {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int v) {
            this.value = v;
        }
    }

    // 前序遍历：头、左、右
    public static void pre(Node head) {
        if (head == null) {
            return;
        }
        System.out.println(head.value);
        pre(head.left);
        pre(head.right);
    }

    // 中序遍历：左、头、右
    public static void mid(Node head) {
        if (head == null) {
            return;
        }
        mid(head.left);
        System.out.println(head.value);
        mid(head.right);
    }

    // 后序遍历：左、右、头
    public static void pos(Node head) {
        if (head == null) {
            return;
        }
        pos(head.left);
        pos(head.right);
        System.out.println(head.value);
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);

        pre(head);
        System.out.println("========");
        mid(head);
        System.out.println("========");
        pos(head);
        System.out.println("========");
    }
}

按层遍历

判断两棵树是否结构相同

思路：

第一颗树的当前节点的left等于第二个树的当前节点的left
第一颗树的当前节点的right等于第二颗树的当前节点的right
边界判断

public class Code04_SameTree {

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    public static boolean isSameTree(TreeNode p, TreeNode q) {
        // ^异或：相同为false，不同为true
        if (p == null ^ q == null) {
            return false;
        }
        if (p == null && q == null) {
            return true;
        }
        // p和q都不为空
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

判断一棵树是否是镜面树

思路：

当前节点的left等于当前节点的right
当前节点的right等于当前节点的left
边界判断

public class Code05_SymmetricTree {

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    public static boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

    public static boolean isMirror(TreeNode h1, TreeNode h2) {
        // ^异或：相同为false，不同为true
        if (h1 == null ^ h2 == null) {
            return false;
        }
        if (h1 == null && h2 == null) {
            return true;
        }
        return h1.val == h2.val && isMirror(h1.left, h2.right) && isMirror(h1.right, h2.left);
    }

}

总结

本节首先介绍了下Java中优先级队列的基本使用，接着用优先级队列解决合并k个有序链表，要求合并后新的链表依然后续的场景。其次简单介绍了下二叉树的递归遍历、判断两课树是否结构相同、判断一棵树是否为镜面树案例code。

新手入门篇-优先级队列、二叉树 2021-06-22 111 阅读3分钟 专栏： 数据结构与算法-灵析社区