# 700. Search in a Binary Search Tree

## 題目敘述

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**7`
• `root` is a binary search tree.
• `1 <= val <= 10**7`

## 解法解析

### 解法範例

#### Go

##### Recursion
``````/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
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
``````/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
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
``````/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} val
* @return {TreeNode}
*/
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
``````/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} val
* @return {TreeNode}
*/
var searchBST = function (root, val) {
while (root && root.val !== val) {
root = root.val > val ? root.left : root.right;
}
return root;
};
``````

#### Kotlin

##### Recursion
``````/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
*     var left: TreeNode? = null
*     var right: TreeNode? = null
* }
*/
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
``````/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
*     var left: TreeNode? = null
*     var right: TreeNode? = null
* }
*/
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
``````/**
* Definition for a binary tree node.
* class TreeNode {
*     public \$val = null;
*     public \$left = null;
*     public \$right = null;
*     function __construct(\$val = 0, \$left = null, \$right = null) {
*         \$this->val = \$val;
*         \$this->left = \$left;
*         \$this->right = \$right;
*     }
* }
*/
class Solution
{

/**
* @param TreeNode \$root
* @param Integer \$val
* @return TreeNode
*/
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
``````/**
* Definition for a binary tree node.
* class TreeNode {
*     public \$val = null;
*     public \$left = null;
*     public \$right = null;
*     function __construct(\$val = 0, \$left = null, \$right = null) {
*         \$this->val = \$val;
*         \$this->left = \$left;
*         \$this->right = \$right;
*     }
* }
*/
class Solution
{

/**
* @param TreeNode \$root
* @param Integer \$val
* @return TreeNode
*/
function searchBST(\$root, \$val)
{
while (\$root != null && \$root->val != \$val) {
\$root = \$root->val > \$val ? \$root->left : \$root->right;
}
return \$root;
}
}
``````

#### Python

##### Recursion
``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
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
``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
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
``````// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
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
``````// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
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
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     public var val: Int
*     public var left: TreeNode?
*     public var right: TreeNode?
*     public init() { self.val = 0; self.left = nil; self.right = nil; }
*     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
*     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
*         self.val = val
*         self.left = left
*         self.right = right
*     }
* }
*/
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
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     public var val: Int
*     public var left: TreeNode?
*     public var right: TreeNode?
*     public init() { self.val = 0; self.left = nil; self.right = nil; }
*     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
*     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
*         self.val = val
*         self.left = left
*         self.right = right
*     }
* }
*/
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
}
}
``````