Search in a Binary Search Tree
BST の root と整数 val が与えられる。値が val に等しいノードを根とする部分木を返す。存在しなければ 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:
- 木のノード数は の範囲
rootは有効な BST
使用した概念Binary Search Tree
アプローチ
思考
- BST の性質を使い、
valと現ノード値を比較しながら左右に下りる - ループで実装すると再帰スタックを使わず安全
実装
from typing import Optional
class TreeNode:
def __init__(self, val: int = 0, left: 'Optional[TreeNode]' = None, right: 'Optional[TreeNode]' = None):
self.val = val; self.left = left; self.right = right
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
node = root
while node is not None:
if val == node.val:
return node
elif val < node.val:
node = node.left
else:
node = node.right
return NoneTime Space