題目敘述
You are given the root of a binary search tree (BST) and an integer val.
Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.
Example 1:
Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]
Example 2:
Input: root = [4,2,7,1,3], val = 5
Output: []
Constraints:
- The number of nodes in the tree is in the range
[1, 5000].
1 <= Node.val <= 10**7root is a binary search tree.1 <= val <= 10**7
題目翻譯
這題的需求很簡單就跟標題一樣，要在二元搜尋數中找出跟參數 val 一樣的節點，並且回傳以該節點為根節點的子樹。如果沒有相同值的節點，就回傳 null。
解法解析
可以看到下面的範例，基本上的解法就可以分為兩種：Recursion 和 Iteration。Iteration 的方式看起來是最好的，在跟 Recursion 差不多的時間複雜度下，有更好的空間複雜度。這邊真的想抱怨 Rust 怎麼取個屬性這麼麻煩，寫起來真煩一長串的。
解法範例
Go
Recursion
func searchBST(root *TreeNode, val int) *TreeNode {
if root == nil || root.Val == val {
return root
}
if root.Val > val {
return searchBST(root.Left, val)
} else {
return searchBST(root.Right, val)
}
}
Iteration
func searchBST(root *TreeNode, val int) *TreeNode {
for root != nil && root.Val != val {
if root.Val > val {
root = root.Left
} else {
root = root.Right
}
}
return root
}
JavaScript
Recursion
var searchBST = function (root, val) {
if (!root || root.val === val) return root;
return root.val > val
? searchBST(root.left, val)
: searchBST(root.right, val);
};
Iteration
var searchBST = function (root, val) {
while (root && root.val !== val) {
root = root.val > val ? root.left : root.right;
}
return root;
};
Kotlin
Recursion
class Solution {
fun searchBST(root: TreeNode?, `val`: Int): TreeNode? {
return when {
root == null -> null
root.`val` == `val` -> root
root.`val` > `val` -> searchBST(root.left, `val`)
else -> searchBST(root.right, `val`)
}
}
}
Iteration
class Solution {
fun searchBST(root: TreeNode?, `val`: Int): TreeNode? {
var cur = root
while (cur != null && cur.`val` != `val`) {
if (cur.`val` > `val`) {
cur = cur.left
} else {
cur = cur.right
}
}
return cur
}
}
PHP
Recursion
class Solution
{
function searchBST($root, $val)
{
if ($root == null || $root->val == $val) {
return $root;
}
return $root->val > $val ? $this->searchBST($root->left, $val) : $this->searchBST($root->right, $val);
}
}
Iteration
class Solution
{
function searchBST($root, $val)
{
while ($root != null && $root->val != $val) {
$root = $root->val > $val ? $root->left : $root->right;
}
return $root;
}
}
Python
Recursion
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if root is None or val == root.val:
return root
return self.searchBST(root.left, val) if val < root.val \
else self.searchBST(root.right, val)
Iteration
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
while root is not None and root.val != val:
root = root.left if val < root.val else root.right
return root
Rust
Recursion
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn search_bst(root: Option<Rc<RefCell<TreeNode>>>, val: i32) -> Option<Rc<RefCell<TreeNode>>> {
if root.is_none() || root.as_ref().unwrap().borrow().val == val {
return root;
}
if root.as_ref().unwrap().borrow().val > val {
return Self::search_bst(root.as_ref().unwrap().borrow().left.clone(), val);
} else {
return Self::search_bst(root.as_ref().unwrap().borrow().right.clone(), val);
}
}
}
Iteration
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn search_bst(root: Option<Rc<RefCell<TreeNode>>>, val: i32) -> Option<Rc<RefCell<TreeNode>>> {
let mut node = root;
while let Some(rc_node) = node.clone() {
let cur_node = rc_node.borrow();
if rc_node.borrow().val == val {
return Some(rc_node.clone());
}
if rc_node.borrow().val > val {
node = rc_node.borrow().left.clone();
} else {
node = rc_node.borrow().right.clone();
}
}
None
}
}
Swift
Recursion
class Solution {
func searchBST(_ root: TreeNode?, _ val: Int) -> TreeNode? {
if root == nil || root!.val == val {
return root
}
return searchBST(root!.val > val ? root!.left : root!.right, val)
}
}
Iteration
class Solution {
func searchBST(_ root: TreeNode?, _ val: Int) -> TreeNode? {
var current = root
while current != nil && current!.val != val {
current = current!.val > val ? current!.left : current!.right
}
return current
}
}
