二叉搜索树与双向链表

剑指 Offer 36. 二叉搜索树与双向链表 - 力扣（Leetcode）

题目要求

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

img-202212201015780

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

img-202212201015070

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

思路分析

我们发现二叉树转换的双向链表顺序其实就是二叉树中序遍历结果的顺序；

  1. 进行中序遍历，将pre指针指向第一个节点，cur指针指向第二个节点，进入循环；
  2. pre.right = cur;
  3. cur.left = pre;
  4. pre=cur;

代码实现

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
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    public Node treeToDoublyList(Node root) {
        // 特殊情况
        if(root == null){
            return null;
        }
        // 中序遍历，使用队列存放
        Queue<Node> queue = new LinkedList<>();
        inOrder(root,queue);
        // 出队列 进行拼接
        Node head = queue.poll();
        Node pre = head;
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            pre.right = cur;
            cur.left = pre;
            pre = cur;
        }
        pre.right = head;
        head.left = pre;
        return head;
    }
    // 中序遍历
    void inOrder(Node root,Queue<Node> queue){
        if(root == null){
            return;
        }
        inOrder(root.left,queue);
        queue.add(root);
        inOrder(root.right,queue);
    }
}

序列化二叉树

剑指 Offer 37. 序列化二叉树 - 力扣（Leetcode）

题目要求

请实现两个函数，分别用来序列化和反序列化二叉树。

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

例子：

img-202212201126300

1
2
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

思路分析

序列化：保存前序遍历结果，保存到数组中，然后使用split分割为字符串；

反序列化：定义一个队列，将头节点放入，进入循环；1. 出队，2. 构建左右子节点(i++)，如果左右子节点不为空则需要入队；重复1和2，直到循环结束；

代码实现

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
65
66
67
68
69
70
71
72
73
74
75
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        // 序列化成字符串
        // 特殊情况
        if(root == null){
            return "";
        }
        // 创建StringBuilder和队列
        StringBuilder build = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root); // 头节点加入队列
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            if(t!=null){
                queue.add(t.left);
                queue.add(t.right);
                // 拼接
                build.append(t.val+ ",");
            }else{
                // 拼接null
                build.append("null,");
            }
        }
        return build.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        // 反序列化
        // 特殊情况
        if(data == null || data.length()<=0){
            return null;
        }
        // 切割为String数组
        String[] str = data.split(",");
        // 定义队列
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(str[0]));
        queue.add(root);
        int i = 1;
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            // 构建左子节点
            if(!str[i].equals("null")){
                TreeNode left = new TreeNode(Integer.parseInt(str[i]));
                t.left = left;
                queue.add(left);
            }
            i++;
            // 构建右子节点
            if(!str[i].equals("null")){
                TreeNode right = new TreeNode(Integer.parseInt(str[i]));
                t.right = right;
                queue.add(right);
            }
            i++;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

字符串的排列

剑指 Offer 38. 字符串的排列 - 力扣（Leetcode）

题目要求

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

例子：

1
2
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

提示：

1 <= s 的长度 <= 8

思路分析

使用全排列解决

  1. 将字符串的所有排列放入数组；
  2. 进入dfs，进行剪枝(arr[i] = arr[i-1] && arr[i-1] = false; 满足就不递归，否则就递归)；
  3. 使用visited[i] = true，表示已经被访问；然后使用for循环对未访问过的元素进行dfs;

代码实现

时间O(n*n!) 空间O(n)

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
class Solution {
    List<Character> path; // 临时访问路劲
    List<String> res; // 结果集
    boolean[] visited; // 记录是否被访问过
    public String[] permutation(String s) {
        // 初始化
        this.path = new ArrayList<>();
        this.res = new ArrayList<>();
        this.visited = new boolean[s.length()];
        // 将String转换为char[]
        char[] arr = s.toCharArray();
        Arrays.sort(arr); //进行排序
        // 调用dfs
        dfs(arr,0);
        // 定义一个String[]
        String[] str = new String[res.size()]; 
        for(int i=0;i<res.size();i++){
            str[i] = res.get(i);
        }
        return str;
    }
    // 深度优先搜索
    void dfs(char[] arr,int k){
        if(arr.length == k){
            // 找到可行路径，放入结果集
            res.add(listToString(path));
            return;
        }
        // 进行n叉树搜索(全排列)
        for(int i=0;i<arr.length;i++){
            // 优化(剪枝)
            if(i>0 && arr[i] == arr[i-1] && visited[i-1] == false){
                // 是相邻字符，且前一个字符未被访问过，说明是同一层的，不是同一路径
                continue; // 不进行操作
            }
            // 全排列
            if(visited[i] == false){
                // 递归访问
                visited[i] = true;
                path.add(arr[i]);
                dfs(arr,k+1);
                path.remove(path.size() - 1); // 回溯移除path最后一个值
                visited[i] = false; // 改为还未访问过
            }
        }
    }
    // list 转换为 String
    String listToString(List<Character> list){
        StringBuilder build = new StringBuilder();
        for(int i=0;i<list.size();i++){
            build.append(list.get(i));
        }
        return build.toString();
    }
}

数组中出现次数超过一半的数字

剑指 Offer 39. 数组中出现次数超过一半的数字 - 力扣（Leetcode）

题目要求

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

例子：

1
2
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

提示：

1 <= 数组长度 <= 50000

思路分析

  1. 哈希表，使用哈希表存放数值以及数值出现的次数，然后和12n{1\over 2}n进行比较；(O(n) O(n))
  2. 排序法，中位数一定是众数；(O(nlogn) O(1))
  3. 摩尔投票法，(O(n) O(1))：
    • 众数的票数是sum;
    • x统计票数最多的那个值；

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int majorityElement(int[] nums) {
        // 特殊情况判断
        if(nums.length <= 2){
            return nums[0];
        }
        int x = nums[0];
        int sum = 1; // 记录众数

        for(int i=1;i<nums.length;i++){
            if(sum == 0){
                x = nums[i];
                sum = 1;
            }else{
                if(x == nums[i]){
                    sum++;
                }else{
                    sum--;
                }
            }
        }
        return x;
    }
}

最小的k个数

剑指 Offer 40. 最小的k个数 - 力扣（Leetcode）

题目要求

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

例子：

1
2
3
4
5
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

输入：arr = [0,1,2,1], k = 1
输出：[0]

提示：

  • 0 <= k <= arr.length <= 10000
  • 0 <= arr[i] <= 10000

思路分析

快速排序思想：选定一个点，把小于等于这个点的放到它的左边，大于这个点的放到它的右边；

堆排序：

  • 定义一个大顶堆：Queue<Integer> heap = new PriorityQueue<>(k, (i1, i2) -> Integer.compare(i2, i1));
  • 通过k控制堆的大小，遍历数组，并将小于堆顶的元素放入；
  • 当堆中元素数量超过k，就将堆中最大的一个元素弹出；
  • 直到遍历完毕，将堆中剩余的元素重新放入一个数组，返回即可；

代码实现

快排思想

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
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        // 特殊情况
        if(arr == null || arr.length == 0 || k == 0){
            return new int[0];
        }
        return quickFind(arr,0,arr.length-1,k);
    }
    // 快速排序
    int[] quickFind(int[] arr,int left,int right,int k){
        int i = partition(arr,left,right);
        if(i+1 == k){
            // 将数组前面k个数进行拷贝
            return Arrays.copyOf(arr,k);
        }
        if(i+1 > k){
            return quickFind(arr,0,i-1,k);
        }else{
            return quickFind(arr,i+1,right,k);
        }
    }
    // 元素下标
    int partition(int[] arr,int left,int right){
        int pivot = arr[left];
        int i = left+1;
        int j = right;
        while(i<j){
            while(i<=j && arr[i]<=pivot) i++;
            while(i<=j && arr[j]>=pivot) j--;
            if(i>=j){
                break;
            }
            // 交换
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        arr[left] = arr[j];
        arr[j] = pivot;
        // 返回pivot下标
        return j;
    }
}

堆排序

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
class Solution {
   public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }
        // 使用一个最大堆（大顶堆）
        // Java 的 PriorityQueue 默认是小顶堆，添加 comparator 参数使其变成最大堆
        Queue<Integer> heap = new PriorityQueue<>(k, (i1, i2) -> Integer.compare(i2, i1));

        for (int e : arr) {
            // 当前数字小于堆顶元素才会入堆
            if (heap.isEmpty() || heap.size() < k || e < heap.peek()) {
                heap.offer(e);
            }
            if (heap.size() > k) {
                heap.poll(); // 删除堆顶最大元素
            }
        }

        // 将堆中的元素存入数组
        int[] res = new int[heap.size()];
        int j = 0;
        for (int e : heap) {
            res[j++] = e;
        }
        return res;
    }
}