标签： 二叉搜索树

目标

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。

当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订 。

日程可以用一对整数 startTime 和 endTime 表示，这里的时间是半开区间，即 [startTime, endTime), 实数 x 的范围为， startTime <= x < endTime 。

实现 MyCalendar 类：

• MyCalendar() 初始化日历对象。
• boolean book(int startTime, int endTime) 如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true 。否则，返回 false 并且不要将该日程安排添加到日历中。

示例：

输入：
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
输出：
[null, true, false, true]
解释：
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False ，这个日程安排不能添加到日历中，因为时间 15 已经被另一个日程安排预订了。
myCalendar.book(20, 30); // return True ，这个日程安排可以添加到日历中，因为第一个日程安排预订的每个时间都小于 20 ，且不包含时间 20 。

说明：

• 0 <= start < end <= 10^9
• 每个测试用例，调用 book 方法的次数最多不超过 1000 次。

提示：

• Store the events as a sorted list of intervals. If none of the events conflict, then the new event can be added.

思路

判断给定区间是否与已有区间相交，如果不相交将其加入已有区间。

最直接的想法是枚举每一个区间，判断是否相交，如果不相交则加入集合。判断区间 [a, b) 与 [c, d) 是否相交，可以固定一个区间，然后让另一个区间滑动，可以发现相交需要满足 d > a && c < b，注意取等号是不相交的。

当然也可以使用二叉搜索树。

TreeSet 中查找特定元素的 API：

• ceiling 返回的是 大于等于 target 的最小元素/ null
• floor 返回的是 小于等于 target 的最大元素/ null
• higher 返回的是 大于 target 的最小元素 / null
• lower 返回的是 小于 target 的最大元素 / null

代码

/**
 * @date 2025-01-02 9:58
 */
class MyCalendar {

    TreeSet<int[]> ts = new TreeSet<>((a, b) -> a[0] - b[0]);

    public MyCalendar() {

    }

    public boolean book(int startTime, int endTime) {
        int[] interval = {startTime, endTime};
        if (ts.isEmpty()) {
            ts.add(interval);
            return true;
        }
        int[] param = new int[]{endTime, 0};
        // 查找 起点 大于等于 endTime 的 起点最小的区间，即要插入间隙的右边区间 right
        int[] right = ts.ceiling(param);
        // 如果 right 是第一个元素 或者 前面一个区间的右边界 end 小于等于 startTime，说明不相交
        if (right == ts.first() || ts.lower(param)[1] <= startTime) {
            ts.add(interval);
            return true;
        }
        return false;
    }

}

性能

目标

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

思路

我第一次想到的方法是先找到这两个指定节点，然后交替求取位置索引较大节点的父节点。然后比较，如果值相等则为公共祖先。但是，题目给出的树结构中不包含指向父节点的引用，很自然地想到先将值保存到数组中，中序遍历二叉搜索树得到正序序列。然后二分查找出index，计算父节点index：左孩是奇数index，父index为(child-1)/2，右孩是偶数index，父index为(child-2)/2，注意排除root，index为0。接着比较父节点的值，还应该考虑输入节点本身就是父子关系的情况，如果pindex > qindex，应先求p节点的父index，因为index大，层数可能更高。再与qindex对应的值比较，不相等的话再求q节点的父index，依此类推。题目中有提到，树中的值都是唯一的。这个想法看起来正确，但真正去实现的时候就会发现是不可行的。首先是存储空间问题，要在数组中保留树的结构，在有许多空节点的情况下是不可行的。这个在 二叉搜索树最近节点查询 中提到过。然后是二分查找需要先排序的问题，这本身就打乱了树节点的index关系。

这几天刷题有一个感受，就是如果算法实现起来太过复杂那么一定是有问题的，很有可能是求解的方向不对。

于是我换了一种思路，还是先找到这两个节点，但是在找的过程中记录下访问的路径，然后再找到路径节点中所有相同节点中的最后一个即可。那么路径应该保存到哪里，又如何获取相同节点序列的最后一个呢？

在 Java 的标准库中，java.util.Stack 类是使用数组实现的。然而，从 Java 6 开始，java.util.Stack 类被标记为遗留（legacy），并建议使用 java.util.Deque 接口及其实现（如 ArrayDeque 或 LinkedList）来替代。Deque 接口表示双端队列，它支持在两端插入和删除元素，因此非常适合实现栈和队列。----AI的回答

无论是使用数组还是链表，最后查找的时候，都可以从头开始同时比较，直到第一个不相等节点出现即可。无需额外申请空间。

如果从尾开始比较的话，需要借助HashSet，将其中一个路径序列存入集合，然后循环弹另一个路径栈，第一个在集合中的被弹出元素就是最近的公共祖先。需要额外的空间。有的时候条件反转一下可以简化处理逻辑，而有时则相反！

另外数组长度固定，超过的话就会有重新分配空间的开销。

代码

public TreeNode lowestCommonAncestor_v1(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> pStack = findPath(root, p.val, new Stack<>());
        Stack<TreeNode> qStack = findPath(root, q.val, new Stack<>());
        HashSet<Integer> set = new HashSet<>();
        while (!pStack.empty()){
            set.add(pStack.pop().val);
        }
        TreeNode res = null;
        while (!qStack.empty()){
            res = qStack.pop();
            if (set.contains(res.val)) {
                break;
            }
        }
        return res;
    }

public Stack<TreeNode> findPath(TreeNode subRoot, int value, Stack<TreeNode> stack) {
    stack.push(subRoot);
    if (subRoot.val == value) {
        return stack;
    } else if (subRoot.val > value) {
        return findPath(subRoot.left, value, stack);
    } else {
        return findPath(subRoot.right, value, stack);
    }
}

/**
 * 还有一个更好的做法是一次遍历同时比较p,q，如果一个大于等于，一个小于等于 当前节点值，表明已经/准备分叉了
 * 这个是看了题解之后发现的
 */
public TreeNode lowestCommonAncestor_v2(TreeNode root, TreeNode p, TreeNode q) {
    if (root.val > p.val && root.val > q.val) {
        return lowestCommonAncestor_v2(root.left, p, q);
    } else if (root.val < p.val && root.val < q.val) {
        return lowestCommonAncestor_v2(root.right, p, q);
    } else {
        return root;
    }
}

性能

目标

给你一个 二叉搜索树 的根节点 root ，和一个由正整数组成、长度为 n 的数组 queries 。

请你找出一个长度为 n 的 二维 答案数组 answer ，其中 answer[i] = [mini, maxi] ：

• mini 是树中小于等于 queries[i] 的 最大值 。如果不存在这样的值，则使用 -1 代替。
• maxi 是树中大于等于 queries[i] 的 最小值 。如果不存在这样的值，则使用 -1 代替。

返回数组 answer 。

说明：

• 树中节点的数目在范围 [2, 10^5] 内
• 1 <= Node.val <= 10^6
• n == queries.length
• 1 <= n <= 10^5
• 1 <= queries[i] <= 10^6

思路

这个题目求的是最接近给定值的节点值。一个朴素的想法是将搜索树的值都列出来，然后从中查找前后的值。这里列出值无需保留树的结构，虽然节点数目范围是[2,10^5]，但如果考虑一个极端的情况，树的深度就是10^5-1，保留树的结构就大约需要2^(10^5)约等于10^3010个元素。二叉搜索树如果采用中序遍历结果就是正序的。但是考虑到存在null值，数组可能填不满，这样就破坏了有序性。想要使用二分查找还要先排序。Arrays.binarySearch 的结果如果找到相应的值则返回对应的index>=0。如果没有找到，则返回-insertion point-1。所谓插入点，其前一个位置的值小于搜索的值。例如 arr = [2, 3, 4, 5, 6, 7, 9] 搜索值为8，使用二分查找则返回 -6-1，arr[5]的值是7，8应该插入到7后面，即插入点为6。因此，如果没查询到，可以使用-index-1得到最近的大于搜索值的位置，这里需要注意数组的边界。

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @date 2024-02-24 18:57
 */
public class ClosestNodes {
    public static 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;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    public final int MAX = 100000;
    public int[] values = new int[MAX];
    public int i = 0;

    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        Arrays.fill(values, -1);
        traverseSubTree(root);
        // 遍历之后values并非全部有序，因为存在null节点，没初始化 值为0
        Arrays.sort(values);
        List<List<Integer>> res = new ArrayList<>(queries.size());
        for (Integer query : queries) {
            List<Integer> tmp = new ArrayList<>(2);
            int ri = Arrays.binarySearch(values, query);
            if (ri < 0) {
                ri = -ri - 1;
                if (ri == values.length) {
                    tmp.add(values[values.length -1]);
                    tmp.add(-1);
                } else if(ri == 0){
                    tmp.add(-1);
                    tmp.add(values[0]);
                } else {
                    tmp.add(values[ri - 1]);
                    tmp.add(values[ri]);
                }
            } else {
                // 如果存在
                tmp.add(values[ri]);
                tmp.add(values[ri]);
            }
            res.add(tmp);
        }
        return res;
    }

    public void traverseSubTree(TreeNode subTree) {
        if (subTree.left != null) {
            traverseSubTree(subTree.left);
        }
        values[i++] = subTree.val;
        if (subTree.right != null) {
            traverseSubTree(subTree.right);
        }
    }
}

性能