You are given the root of a binary search tree and an array queries of size n consisting of positive integers.
Find a 2D array answer of size n where answer[i] = [mini, maxi]:
mini is the largest value in the tree that is smaller than or equal to queries[i]. If a such value does not exist, add -1 instead. maxi is the smallest value in the tree that is greater than or equal to queries[i]. If a such value does not exist, add -1 instead. Return the array answer.
Example 1:
Input: root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]
Output: [[2,2],[4,6],[15,-1]]
Explanation: We answer the queries in the following way:
- The largest number that is smaller or equal than 2 in the tree is 2, and the smallest number that is greater or equal than 2 is still 2. So the answer for the first query is [2,2].
- The largest number that is smaller or equal than 5 in the tree is 4, and the smallest number that is greater or equal than 5 is 6. So the answer for the second query is [4,6].
- The largest number that is smaller or equal than 16 in the tree is 15, and the smallest number that is greater or equal than 16 does not exist. So the answer for the third query is [15,-1].
Example 2:
Input: root = [4,null,9], queries = [3]
Output: [[-1,4]]
Explanation: The largest number that is smaller or equal to 3 in the tree does not exist, and the smallest number that is greater or equal to 3 is 4. So the answer for the query is [-1,4].
Constraints:
The number of nodes in the tree is in the range [2, 105].
1 <= Node.val <= 106
n == queries.length
1 <= n <= 105
1 <= queries[i] <= 106
题意：给定一个二叉搜索树，和一批查询值，做批量查询
如果查找到返回[target, target], 否则返回最近存在的值，如果不存在最近值用-1表示
思路一：先序遍历查值
其实就是利用二叉搜索树的特性
如果节点值比target大，则走left路径
如果节点值比target小，则走right路径
该方法只能通过52/53的case，对于极度不平衡的搜索二叉树TLE，多用一个map在前面查询，命中就不查树了这样可以AC，但是挺沙雕的。。
思路二：把搜索二叉树dump成一个数组
做二分查找。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func closestNodes(root *TreeNode, queries []int) [][]int {
res := make([][]int, 0, len(queries))
tMap := make(map[int]bool, 0)
buildMap(root, tMap)
for _, x := range queries {
if tMap[x] {
res = append(res, []int{x, x})
continue
}
subRes := []int{-1, -1}
query(root, x, &subRes)
res = append(res, subRes)
}
return res
}
func query(node *TreeNode, target int, res *[]int) {
if node == nil {
return
}
if node.Val == target {
(*res)[0], (*res)[1] = target, target
return
}
if target < node.Val {
(*res)[1] = node.Val
query(node.Left, target, res)
return
}
(*res)[0] = node.Val
query(node.Right, target, res)
return
}
func buildMap(node *TreeNode, tMap map[int]bool) {
if node == nil {
return
}
tMap[node.Val] = true
buildMap(node.Left, tMap)
buildMap(node.Right, tMap)
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func closestNodes(root *TreeNode, queries []int) [][]int {
vals := make([]int, 0, 100000)
trans2Slice(root, &vals)
res := make([][]int, 0, len(queries))
for _, q := range queries {
subRes := bs(vals, 0, len(vals)-1, q)
res = append(res, subRes)
}
return res
}
func trans2Slice(node *TreeNode, vals *[]int) {
if node == nil {
return
}
trans2Slice(node.Left, vals)
*vals = append(*vals, node.Val)
trans2Slice(node.Right, vals)
}
func bs(vals []int, left, right, target int) []int {
res := []int{-1, -1}
for left <= right {
mid := (left + right) / 2
if vals[mid] == target {
res[0], res[1] = target, target
return res
}
if vals[mid] < target {
left = mid+1
res[0] = vals[mid]
} else {
right = mid-1
res[1] = vals[mid]
}
}
return res
}