2476.二叉搜索树最近节点查询

链接：2476.二叉搜索树最近节点查询
难度：Medium
标签：树、深度优先搜索、二叉搜索树、数组、二分查找、二叉树
简介：给你一个 二叉搜索树 的根节点 root ，和一个由正整数组成、长度为 n 的数组 queries 。

题解 1 - python

• 编辑时间：2024-02-24
• 执行用时：582ms
• 内存消耗：74.37MB
• 编程语言：python
• 解法介绍：dfs后排序处理queries。

class Solution:
    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
        arr = []
        def inorder(node: Optional[TreeNode]):
            if not node: return
            inorder(node.left)
            arr.append(node.val)
            inorder(node.right)
        inorder(root)
        idx = 0
        ans = [[] for _ in range(len(queries))]
        queries = sorted((q, i) for i, q in enumerate(queries))
        for q, i in queries:
            while idx < len(arr) and arr[idx] < q:
                idx += 1
            ans[i] = [-1, -1]
            if idx < len(arr) and arr[idx] == q:
                ans[i] = [q, q]
            else:
                if idx > 0: ans[i][0] = arr[idx - 1]
                if idx < len(arr): ans[i][1] = arr[idx]
        return ans

题解 2 - cpp

• 编辑时间：2022-11-20
• 执行用时：308ms
• 内存消耗：150.5MB
• 编程语言：cpp
• 解法介绍：bs。

// bestlyg
# define X first
# define Y second
# define lb(x) ((x) & (-x))
# define mem(a,b) memset(a,b,sizeof(a))
# define debug freopen("r.txt","r",stdin)
# define pi pair<int,int>
#ifdef DEBUG
#define log(frm, args...) {    printf(frm, ##args);}
#else
#define log(frm, args...)
#endif
typedef long long ll;
using namespace std;
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> list;
    vector<vector<int>> ans;
    vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
        dfs(root);
        for (auto &q : queries) {
            vector<int> item(2);
            item[0] = find1(q);
            item[1] = find2(q);
            ans.push_back(item);
        }
        return ans;
    }
    void dfs(TreeNode *node) {
        if (!node) return;
        dfs(node->left);
        list.push_back(node->val);
        dfs(node->right);
    }
    int find1(int q) {
        int l = -1, r = list.size() - 1, m;
        while (l < r) {
            m = (l + r + 1) / 2;
            if (list[m] > q) r = m - 1;
            else l = m;
        }
        if (l == -1) return l;
        return list[l];
    }
    int find2(int q) {
        int l = 0, r = list.size(), m;
        while (l < r) {
            m = (l + r) / 2;
            if (list[m] >= q) r = m;
            else l = m + 1;
        }
        if (l == list.size()) return -1;
        return list[l];
    }
};