MediumRating 1597

2476. Closest Nodes Queries in a Binary Search Tree

arraybinary-searchtreedepth-first-searchbinary-search-treebinary-tree

在 LeetCode 上作答 ↗

解題說明

Closest Nodes Queries in a Binary Search Tree

題目描述：給定一棵二元搜尋樹（BST）的根節點和一組查詢值，對每個查詢值 q，找出樹中 <= q 的最大值和 >= q 的最小值。若不存在則返回 -1。

解題思路：由於給定的 BST 不一定平衡，直接在樹上查詢可能退化為 O(n)。最佳做法是先中序遍歷得到排序陣列，然後對每個查詢用二分搜尋。

中序遍歷 BST 得到排序序列後，對每個查詢 q：

用 upper_bound 找到第一個 > q 的位置，前一個即為 <= q 的最大值
用 lower_bound 找到第一個 >= q 的位置，即為 >= q 的最小值

C++ 解法

複雜度分析

時間複雜度：O(n + m log n) — 中序遍歷 O(n)，每次查詢二分搜尋 O(log n)，共 m 次查詢

空間複雜度：O(n) — 儲存中序遍歷結果的陣列

虛擬碼

1. Perform inorder traversal of BST to get sorted array
2. For each query q:
   a. Binary search (upper_bound) for first element > q
      - If predecessor exists, lo = predecessor value; else lo = -1
   b. Binary search (lower_bound) for first element >= q
      - If found, hi = that value; else hi = -1
   c. Append [lo, hi] to result
3. Return result

其他解法

直接 BST 搜尋：對每個查詢在 BST 上搜尋，追蹤最近的 <= 和 >= 值。平均 O(log n) 但最壞 O(n)（不平衡 BST）。如果 BST 保證平衡則此法更優（省去排序步驟）。
平衡 BST 重建：先將 BST 轉為排序陣列，再建平衡 BST，然後在平衡樹上查詢。但不如直接在排序陣列上二分搜尋簡單。

延伸思考

如果 BST 會動態插入和刪除節點，同時需要回答這類查詢，用什麼資料結構最合適？
如果查詢要求的是「嚴格小於」和「嚴格大於」而非 <= 和 >=，如何修改二分搜尋？
如果還需要返回第 k 近的節點值（而非最近的），如何擴展演算法？

Closest Nodes Queries in a Binary Search Tree — CaffeCode