06 比较器、二叉树相关题目

1 比较器的运用

public class MyComparator implements Comparator<Integer> {
    /**
     * 返回负数，先排o1，返回正数，先排o2，返回0，随意
     * @param o1 第一个数
     * @param o2 第2个数
     * @return 返回比较结果
     */
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}

2 合并多个有序链表

leetcode:https://leetcode.com/problems/merge-k-sorted-lists/
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }
        //优先级队列，实现小根堆
        PriorityQueue<ListNode> listNodes = new PriorityQueue<>(new ListNodeComparator());
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                listNodes.add(lists[i]);
            }
        }
        if (listNodes.isEmpty()) {
            return null;
        }
        ListNode head = listNodes.poll();
        ListNode pre = head;
        if (pre.next != null) {
            listNodes.add(pre.next);
        }
        while (!listNodes.isEmpty()) {
            ListNode cur = listNodes.poll();
            pre.next = cur;
            pre = cur;
            if (cur.next != null) {
                listNodes.add(cur.next);
            }
        }
        return head;
    }
    //自定义比较器
    class ListNodeComparator implements Comparator<ListNode> {
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    }

3 二叉树遍历

二叉树遍历三种方式：
先序：头、左、右
中序：左、头、右
后序：左、右、头

理解递归序

//二叉树节点定义
static class Node {
        int val;
        Node left;
        Node right;

        public Node(int val) {
            this.val = val;
        }
    }
//二叉数遍历（递归）
    public static void traversalBinaryTree(Node node){
        if (node==null){
            return;
        }

        //System.out.print(node.val+ " ");  先序
        traversalBinaryTree(node.left);
        //System.out.print(node.val+ " ");  中序
        traversalBinaryTree(node.right);
        //System.out.print(node.val+ " ");  后序

    }

4 判断两颗树是否结构相同

leetcode:https://leetcode-cn.com/problems/same-tree/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

//二叉树节点定义    
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null ^ q == null) {
            return false;
        }

        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

    }

5 判断一棵树是否是镜面树

leetcode:https://leetcode.com/problems/symmetric-tree/

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

    public boolean symmetric(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        }
        if (node1 == null ^ node2 == null) {
            return false;
        }

        return node1.val == node2.val && symmetric(node1.left, node2.right) && symmetric(node1.right, node2.left);
    }

6 返回一棵树的最大深度

leetcode:https://leetcode.com/problems/maximum-depth-of-binary-tree/
二叉树的最大深度是从根节点到最远的叶节点的最长路径上的节点数。

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

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;

    }

7 用先序数组和中序数组重建一棵树

leetcode:https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
给定两个整数数组preorder和inorder，
其中preorder是二叉树的前序遍历，
inorder是同一棵树的前序遍历，构造并返回二叉树

public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) {
            return null;
        }
        if (preorder.length != inorder.length) {
            return null;
        }
        HashMap<Integer, Integer> hashMap = new HashMap<>(16);
        for (int i = 0; i < inorder.length; i++) {
            hashMap.put(inorder[i], i);
        }
        return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1,hashMap);

    }

    public TreeNode buildTree(int[] preorder, int s, int e, int[] inorder, int s1, int e1, HashMap<Integer, Integer> hashMap) {

        if (s > e) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[s]);
        if (s == e) {
            return root;
        }
        int i = hashMap.get(preorder[s]);

        root.left = buildTree(preorder, s + 1, s + i - s1, inorder, s1, i - 1,hashMap);
        root.right = buildTree(preorder, s + i - s1 + 1, e, inorder, i + 1, e1,hashMap);
        return root;
    }