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

题目来源

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

题目概述

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

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

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

思路分析

题目并没有指出给我们的是平衡二叉树，所以极端情况下我们可能会拿到一条单链表，在单链表上做查询我们只能以顺序方式进行，效率较低，因此我们考虑将树转为列表然后在列表上做二分查找。

代码实现

java实现

public class Solution {
    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        treeToList(root);
        List<List<Integer>> res = new ArrayList<>();
        // 二分查找
        for (Integer query : queries) {
            int min = -1;
            int max = -1;
            int start = 0;
            int end = list.size();
            int mid =  0;
            while (start < end) {
                mid = start + (end - start) / 2;
                if (list.get(mid) >= query) {
                    end = mid;
                } else if (list.get(mid) < query) {
                    start = mid + 1;
                }
            }
            if (start < list.size()) {
                max = list.get(start);
                if (query.equals(max)) {
                    min = query;
                }
            }
            if (min == -1 && start > 0) {
                min = list.get(start - 1);
            }
            List<Integer> temp = new ArrayList<>();
            temp.add(min);
            temp.add(max);
            res.add(temp);
        }
        return res;
    }

    List<Integer> list = new ArrayList<>();

    /**
     * 中序遍历转树为列表
     * @param root
     */
    private void treeToList(TreeNode root) {
        if (root == null) return;
        if (root.left != null) treeToList(root.left);
        list.add(root.val);
        if (root.right != null) treeToList(root.right);
    }
}

c++实现

class Solution {
public:

    /**** 树转列表 *****/
    vector<int> list;
    void tree_to_list(TreeNode* root) {
        if (root == nullptr) return;
        if (root->left != nullptr) tree_to_list(root->left);
        list.push_back(root->val);
        if (root->right != nullptr) tree_to_list(root->right);
    }

    vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
        tree_to_list(root);
        vector<vector<int>> res;
        // 二分查找
        for (int query : queries) {
            int min = -1;
            int max = -1;
            int start = 0;
            int end = list.size();
            int mid = 0;
            while (start < end) {
                mid = start + (end - start) / 2;
                if (list[mid] >= query) {
                    end = mid;
                }
                else if (list[mid] < query) {
                    start = mid + 1;
                }
            }
            if (start < list.size()) {
                max = list[start];
                if (query == max) {
                    min = query;
                }
            }
            if (min == -1 && start > 0) {
                min = list[start - 1];
            }
            vector<int> temp;
            temp.push_back(min);
            temp.push_back(max);
            res.push_back(temp);
        }
        return res;
    }
}