题解 | 二叉搜索树最近节点查询

题干分析

利用二叉搜索树的定义转化一下即：题设给定一颗二叉搜索树，和一个查询值，要求我们找到最接近这个值的两个节点值，如果相等则返回两次节点值，如果为边界节点，另一节点值用-1代替。

算法思路

利用二叉搜索树的中序遍历结果为其所有节点值组成的升序数组的性质，将在二叉搜索树上的查找转化为数组中的二分查找第一个不小于给定值的元素。

注意，二叉搜索树可能退化为一条链，利用二叉搜索树的定义进行查找会超时。

实现代码

class Solution {
    void dfs(TreeNode *node, vector<int> &order) {
        if (node) {
            dfs(node->left, order);
            order.push_back(node->val);
            dfs(node->right, order);
        }
    }
public:
    vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
        vector<vector<int>> ans;
        vector<int> order;
        dfs(root, order);
        for (auto tar : queries) {
            auto it = ranges::lower_bound(order, tar);
            if (it == order.end()) ans.push_back({*order.rbegin(), -1});
            else if (it == order.begin()) {
                if (*it == tar) ans.push_back({tar, tar});
                else ans.push_back({-1, *it});
            }
            else if (*it == tar) ans.push_back({tar, tar});
            else ans.push_back({*(it - 1), *it});
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：递归耗时，查询节点每次， 总计
• 空间复杂度：中序遍历结果暂存，递归最坏，总计