ETH官方钱包

前往
大廳
主題

LeetCode - 2476. Closest Nodes Queries in a Binary Search Tree 解題心得

Not In My Back Yard | 2023-10-15 12:00:11 | 巴幣 0 | 人氣 112

題目連結:


題目意譯:
你被給定一棵二元搜尋樹(Binary Search Tree,BST)的根節點 root 以及一個大小為 n 且由正整數所組成的陣列 queries。

請找到一個大小為 n 的二維陣列 answer,其中 answer[i] = [mini, maxi]:
mini 為在樹中小於或等於 queries[i] 的最大值。如果此值不存在,則設為 -1。
maxi 為在樹中大於或等於 queries[i] 的最小值。如果此值不存在,則設為 -1。

回傳陣列 answer。

限制:
樹中的節點個數位於範圍 [2, 10 ^ 5] 中。
1 ≦ Node.val ≦ 10 ^ 6
n == queries.length
1 ≦ n ≦ 10 ^ 5
1 ≦ queries[i] ≦ 10 ^ 6



範例測資:
範例 1:
輸入: root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]
輸出: [[2,2],[4,6],[15,-1]]
解釋: 我們以下列結果回答每一筆詢問:
在樹中小於等於 2 的最大數為 2。而大於等於 2 的最小值仍為 2。所以對於第一筆詢問的答案為 [2,2]。
在樹中小於等於 5 的最大數為 4。而大於等於 5 的最小值為 6。所以對於第二筆詢問的答案為 [4,6]。
在樹中小於等於 16 的最大數為 15。而大於等於 16 的最小值不存在。所以對於第冤筆詢問的答案為 [15,-1]。

範例 2:
輸入: root = [4,null,9], queries = [3]
輸出: [[-1,4]]
解釋: 在樹中小於等於 3 的最大數並不存在。而大於等於 3 的最小值為 4。所以對於該筆詢問的答案為 [-1,4]。


解題思維:
以前有提及過 BST 的中序探訪(Inorder Traversal)是一個已排序的數列(參見這題)。因此我們可以對這棵二元搜尋樹進行中序探訪來把這些數字存成一個已排序陣列。接著對於每一筆詢問直接進行二分搜尋法(Binary Search)來看詢問的數字位於陣列哪兩個數字之間(或是直接存在於陣列中),並藉著索引值計算所求即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作