【LeetCode】剑指 Offer Ⅱ 第8章：树（12道题） -- Java Version

题库链接：https://leetcode.cn/problem-list/e8X3pBZi/

二叉树是一种典型的具有递归性质的数据结构，二叉树的广度优先搜索通常是通过队列来实现，而二叉树的深度优先搜索可以分为中序遍历、前序遍历和后序遍历。二叉树 DFS 的递归写法非常简单，按照遍历的顺序编写递归顺序即可；而将递归代码改写成迭代的形式则通常需要 栈 来辅助，栈主要用于二叉树左侧节点的存储。
……
而二叉搜索树则是一种特殊的二叉树，在二叉搜索树中进行搜索、添加和删除操作的平均时间复杂度均为 O(logn)，如果按照中序遍历的顺序遍历一棵二叉搜索树，那么则会按照从小到大的顺序依次遍历每个节点。由于这个特性，与二叉搜索树相关的很多面试题都适合使用中序遍历解决。
……
在 Java 中提供了 TreeSet 和 TreeMap 这两种实现了平衡二叉搜索树的数据结构，如果需要动态地在一个排序的数据集合中添加元素，或者需要根据数据的大小查找，那么可以使用 TreeSet 和 TreeMap 解决。
常用方法：

• ceiling()：返回键大于或等于给定值的最小键；如果没有则返回 null
• floor()：返回键小于或等于给定值的最大键；如果没有则返回 null
• higher()：返回键大于给定值的最小键；如果没有则返回 null
• lower()：返回键小于给定值的最大键；如果没有则返回 null

---

1. 剑指 Offer II 047. 二叉树剪枝 – P132

给定一个二叉树 根节点 root ，树的每个节点的值要么是 0，要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。
节点 node 的子树为 node 本身，以及所有 node 的后代。

1.1 递归（深搜）：二叉树的后序遍历 – O(n)（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(h)$

Key：二叉树的后序遍历（左、右、根），一般我们可以用递归（深搜）来实现二叉树的遍历，适用于小树深的情况；而如果是大树深，则更推荐采用迭代的方式（用栈来保存路径）。

/**
 * 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 {
    // Solution1：二叉树后序遍历
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) return null;
        
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        
        if (root.left == null && root.right == null && root.val == 0) {
            return null;  // 将左、右子节点为null, 且自身值为0的节点剪枝
        }
        return root;
    }
}
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

2. 剑指 Offer II 048. 序列化和反序列化二叉树 – P134

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
……
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

2.1 递归（深搜）：二叉树的前序遍历 – O(n)（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(h)$

如何将二叉树序列化成一个字符串：

1. 前序遍历每一个节点；
2. 用分隔符对不同的节点进行分隔；
3. 把 null 节点序列化成一个特殊的字符串，如 ”#“；

……
反序列化则是：

1. 将序列化形成的字符串按分隔符进行分割；
2. ”#“ 与 null 对应；
3. 递归还原节点；

……
细节：方法传参时，传递的是一个只有一个元素的数组，来作为字符串遍历的下标。

/**
 * 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 "#";

        String left =  serialize(root.left);
        String right = serialize(root.right);

        return String.valueOf(root.val)+ "," + left + "," + right;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] strs = data.split(",");
        int[] i = {0};  // 细节，变量传参不会改变值，因此要用数组传参
        return dfs(strs, i);
    }

    public TreeNode dfs(String[] strs, int[] i) {
        String str = strs[i[0]];
        i[0]++;
        if (str.equals("#")) return null;

        TreeNode node = new TreeNode(Integer.parseInt(str));
        node.left = dfs(strs, i);
        node.right = dfs(strs, i);
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
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

3. 剑指 Offer II 049. 从根节点到叶节点的路径数字之和 – P136

给定一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：

• 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。

3.1 递归（深搜）：二叉树的前序遍历 – O(n)（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(h)$

Key：二叉树中路径相关的面试题，通常都可以使用深度优先搜索的方法解决，这是因为路径通常顺着指向子节点的指针的方向，也就是纵向方法。

/**
 * 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 {
    // Solution1：二叉树前序遍历记录路径
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    public int dfs(TreeNode root, int path) {
        if (root == null) return 0;

        path = path * 10 + root.val;  // 记录路径
        if (root.left == null && root.right == null) return path;

        return dfs(root.left, path) + dfs(root.right, path);
    }
}
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

4. 剑指 Offer II 050. 向下的路径节点值之和 – P136

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

4.1 递归（深搜）：二叉树的前序遍历 – O(n)（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(h)$

Key：path 用于记录从根节点出发所经过的路径，map 用于记录累加路径和出现的次数，遍历所有的节点，在这个过程中 path - target 在map 中出现的次数即为二叉树中节点值之和等于 target 的路径的数目。

/**
 * 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 pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> map = new HashMap<>();  // Node.val <= 109, 相加有可能数值溢出
        map.put(0L, 1);  // 赋初值，path - target 
        return dfs(root, targetSum, map, 0);
    }

    public int dfs(TreeNode root, int target, Map<Long, Integer> map, long path) {
        if (root == null) return 0;
        path += root.val;

        int count = map.getOrDefault(path-target, 0);  // 查询当前路径下是否存在符合条件的子路径
        map.put(path, map.getOrDefault(path,0)+1);  // 记录当前路径

        count += dfs(root.left, target, map, path);  // 向左遍历
        count += dfs(root.right, target, map, path);  // 向右遍历

        map.put(path, map.get(path)-1);  // 删除当前路径节点，回到上一路径状态
        return count;
    }
}
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

5. 剑指 Offer II 051. 节点值之和最大的路径 – P139

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。

5.1 递归（深搜）：二叉树的后序遍历 – O(n)（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(h)$

Key：原书题解太过麻烦，推荐 【灵茶山艾府】彻底掌握直径 DP！从二叉树到一般树！（Python/Java/C++/Go），重点是要理解递归思想，递归就像是一个后入先出的栈，一层层递归返回。

/**
 * 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 res = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return res;
    }

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

        int left = dfs(root.left);  // 左子树最大链和
        int right = dfs(root.right);  // 右子树最大链和
        res = Math.max(res, left + right + root.val);  // 两条链拼成路径
        return Math.max(Math.max(left, right) + root.val, 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
30
31
32

6. 剑指 Offer II 052. 展平二叉搜索树 – P142

给你一棵二叉搜索树，请 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

6.1 栈 + 二叉树中序遍历 – O(n)（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(n)$

以中序遍历的顺序，递增式的遍历每个节点，并在遍历的过程中改变节点的指向。

/**
 * 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 {
    // Solution1：二叉树中序遍历
    public TreeNode increasingBST(TreeNode root) {
        Stack<TreeNode> sk = new Stack<>();
        TreeNode cur = root;  // 当前节点
        TreeNode prev = null;  // 前一节点
        TreeNode head = null;  // 展开后的首节点

        while (cur != null || !sk.isEmpty()) {
            while (cur != null) {  // 将以当前节点为首的左侧节点全部入栈
                sk.push(cur);
                cur = cur.left;
            }

            cur = sk.pop();  // 左侧节点以此出栈
            if (prev != null) { 
                prev.right = cur;
            } else {
                head = cur;  // 如果prev为null，说明此时出栈的节点是展开后的头节点
            }

            prev = cur;
            cur.left = null;
            cur = cur.right;  // 继续遍历
        }
        return head;
    }
}
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

7. 剑指 Offer II 053. 二叉搜索树的下一个节点 – P144

给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。
节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。

7.1 中序遍历：二叉搜索树的特性 – O(h)（⭐）

时间复杂度 $O(h)$，空间复杂度 $O(1)$

该题最直观的思路就是采用二叉树的中序遍历，逐一遍历二叉树的每个节点。但由于本题是二叉搜索树，因此我们可以利用二叉搜索树的特性，每当到达一个节点就比较根节点的值和节点 p 的值，如果当前节点的值比节点 p 的值大，我们就暂存其节点，并向其左孩子遍历；如果当前节点的值比节点 p 的值要小，那么我们就向其右孩子遍历，直至找到所有比 p 节点值大的节点中值最小的那一个。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode cur = root;
        TreeNode res = null;  // 返回结果
        while (cur != null) {
            if (cur.val > p.val) {
                res = cur;
                cur = cur.left;  // 当前节点值大于p节点值，暂存当前节点，并寻找大于p节点值中最小的节点
            } else {
                cur = cur.right;
            }
        }
        return res;        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

8. 剑指 Offer II 054. 所有大于或等于节点的值之和 – P146

给定一个二叉搜索树，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

提醒一下，二叉搜索树满足下列约束条件：

• 节点的左子树仅包含键 小于 节点键的节点。
• 节点的右子树仅包含键 大于 节点键的节点。
• 左右子树也必须是二叉搜索树。

8.1 倒序的中序遍历 – O(n)（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(h)$

Key：二叉搜索树的中序遍历按照节点值从小到大按顺序遍历，也就是当遍历到某个节点时比该节点小的节点都已经遍历过了，而本题要求的是将每个节点的值替换成树中大于或者等于该节点值的所有节点值之和，因此可以倒序中序遍历，从右 根 左的顺序，从大到小进行遍历，这样就保证了只需一次遍历即可求出节点值的和。（当然了我们也可以通过两次遍历，第一次先求出所有节点值的和，第二次依次遍历用 total - sum 得到需要的值）

/**
 * 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 {
    // Soultion1：倒序的中序遍历（右 根 左）
    public TreeNode convertBST(TreeNode root) {
        Stack<TreeNode> sk = new Stack<>();
        TreeNode cur = root;
        int sum = 0;
        while (cur != null || !sk.isEmpty()) {
            while (cur != null) {
                sk.push(cur);
                cur = cur.right;
            }

            cur = sk.pop();
            sum += cur.val;
            cur.val = sum;
            cur = cur.left;
        }
        return root;
    }
}
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

9. 剑指 Offer II 055. 二叉搜索树迭代器 – P148

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

• BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
• boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
• int next()将指针向右移动，然后返回指针处的数字。

……
注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

9.1 二叉搜索树中序遍历：过程拆分 – O(1)（⭐）

时间复杂度 $O(1)$，空间复杂度 $O(h)$

该题根据不同的限制条件有不同的解法，如：

1. 可以改变输入的二叉树结构：那么我们就可以将二叉搜索树展平，相当于对链表的遍历；
2. 如果不可以改变输入的二叉树结构：那么我们可以在二叉搜索树遍历的时候用链表将节点记录下来，这样的缺点就是需要使用额外的存储结构；
3. 如果不可以改变输入的二叉树结构，且不能使用额外的存储空间：拆分二叉搜素树中序遍历的过程也是可以的，我们需要理解 二叉搜索树中序遍历 本身的外循环判断条件就可以作为 hasNext 的判断，然后通过 next ，每调用一次，进行一次循环遍历即可。

/**
 * 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 BSTIterator {
    TreeNode cur;
    Stack<TreeNode> sk;

    public BSTIterator(TreeNode root) {  // 构造函数：输入二叉搜索树的根节点初始化该迭代器
        cur = root;
        sk = new Stack<>();
    }
    
    public int next() {  // 返回二叉搜索树中下一个最小的节点的值
        while (cur != null) {
            sk.push(cur);
            cur = cur.left;
        }

        cur = sk.pop();
        int val = cur.val;
        cur = cur.right;
        return val;
    }
    
    public boolean hasNext() {  // 返回二叉搜索树是否还有下一个节点
        return cur != null || !sk.isEmpty();
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */
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

10. 剑指 Offer II 056. 二叉搜索树中两个节点的值之和 – P150

给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。

10.1 中序遍历 + HashSet – O(n)（⭐）

时间复杂度 $O(n)$，空间复杂度 $O(n)$

Key：该题可以看成二叉树版的两数之和，常规做法就是通过顺序遍历，找出该数据结构中的数据是否存在 target - cur.val，如果存在，则说明该数据结构中存在两数之和等于 target，后序进阶可能会要求输出符合条件的两数的下标值，改用 HashMap 在记录值的同时存储下标即可解决。
……
Ps：当然以上做法并未考虑二叉搜索树这一要素，如想进一步优化，我们可以利用二叉搜素树的特点，将时间复杂度降低至 O(h)，通过数组双指针的策略来进行数据的遍历，但需要编写专门的二叉搜索树迭代器（正序和倒序都需要）。

/**
 * 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 findTarget(TreeNode root, int k) {
        Set<Integer> st = new HashSet<>();
        Deque<TreeNode> sk = new ArrayDeque<>();  // stack换成Deque可以提高速度
        TreeNode cur = root;

        while (cur != null || !sk.isEmpty()) {  // 中序遍历
            while (cur != null) {
                sk.push(cur);
                cur = cur.left;
            }
            cur = sk.pop();
            if (st.contains(k-cur.val)) {  // 常规套路（两数之和）
                return true;
            }

            st.add(cur.val);  // 记录每一次遍历到的值
            cur = cur.right;
        } 
        return false;
    }
}
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

11. 剑指 Offer II 057. 值和下标之差都在给定的范围内 – P155

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。

11.1 平衡二叉搜索树：TreeSet – O(nlogn)（⭐）

时间复杂度 $O(nlogn)$，空间复杂度 $O(n)$

Key：该题最常规的做法就是遍历所有数字，然后每遍历到一个数字就判断该数字的前 k 个数字与其差的绝对值是否小于等于 t，这种方法的时间复杂度为 O(nk)。
……
除以上方法外，还有一种巧妙的方法可以时间复杂度降低至 O(n)，此时我们需要借助 HashMap，并通过给遍历的每个数字划分桶号（这里我们可以理解为数据范围，0-t 范围入 0 桶，t+1 - 2t+1范围入 1 桶，以此类推），这样我们只要找到一个桶中有两个数即可判断是否有数字满足条件；如果没有，我们还可以查看当前数字所在桶的前后两桶中是否有数字可以和当前数字组合满足条件，循环遍历一遍即可解决问题。
……
本题下方给出的代码属于另一种方法，属于对 TreeSet 性质的运用，通过 TreeSet 我们可以以 O(logn) 的时间复杂度得出一个数字对应集合中 ≥的最小值，以及 ≤的最大值，对这两个数字进行判断，即可得出当前数字与其前 k 个数字之间的一个数据范围，然后得出答案。

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> set = new TreeSet<>();  // 注意包装类应选择Long，int有溢出风险
        
        for (int i = 0; i < nums.length; i++) {

            Long lower = set.floor((long)nums[i]);  // 下取值，找小最大
            if (lower != null && nums[i] - lower <= t) return true;

            Long higher = set.ceiling((long)nums[i]);  // 上取值，找大最小
            if (higher != null && higher - nums[i] <= t) return true;

            set.add((long) nums[i]);

            if (i >= k) {  // 移除多余数值，set只保留当前数字的前k个数值
                set.remove((long)nums[i-k]);
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

12. 剑指 Offer II 058. 日程表 – P157

请实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内没有其他安排，则可以存储这个新的日程安排。
MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。
当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生重复预订。
每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

12.1 平衡二叉搜索树：TreeMap – O(nlogn)（⭐）

时间复杂度 $O(nlogn)$，空间复杂度 $O(n)$

常规方法：直接遍历，通过 ArrayList 对数据进行存储，每次 book(start, end) 操作都会对 ArrayList 进行一次遍历，比较当前事件是否与已经存在的事件之间存在冲突，如果冲突返回 false，无冲突则将当前事件加入到集合中，并返回 true。
……
利用二叉搜索树的特性：使用 TreeSet 或 TreeMap 对数据进行存储，利用其特有的 API — floorEntry() / ceilEntry() 找出小最大和大最小，然后与当前事件的时间范围进行比较即可，节省了比较次数。
……
还可以使用线段树的方法，详细内容可参考：方法三：线段树

TreeMap 实现的接口、继承的类，如下图所示：

class MyCalendar {
    TreeMap<Integer,Integer> map;  // 写成 Map 不行，会出现 error: cannot find symbol [in MyCalendar.java] 错误，这是因为其中的floorEntry()以及ceilingEntry()方法是源自于public interface NavigableMap接口的。

    public MyCalendar() {
        map = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
        Map.Entry<Integer,Integer> event = map.floorEntry(start);  // 下取值，找到比当前开始时间低的最近的开始事件
        if (event != null && event.getValue() > start) return false;  // 判断找到的事件的结束时间是否超过了当前的开始时间

        event = map.ceilingEntry(start);  // 上取值，找到比当前开始时间高的最近开始事件
        if (event != null && event.getKey() < end) return false;  // 判断找到的事件的开始时间是否早于当前的结束时间

        map.put(start, end);  // 都没有，则说明当前事件符合要求，可以放入集合
        return true;
    }
}
/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar obj = new MyCalendar();
 * boolean param_1 = obj.book(start,end);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

13. 继续提升：加练题目

🎈 可参考：

• 树 · SharingSource/LogicStack-LeetCode Wiki · GitHub
• 二叉树 · SharingSource/LogicStack-LeetCode Wiki · GitHub
• 线段树 · SharingSource/LogicStack-LeetCode Wiki · GitHub