[700] Search in a Binary Search Tree | Leetcode Easy

🔎 문제설명

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.

결과 예시

root의 타입과 반환타입은 TreeNode입니다. 리스트형식 아닙니다.

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: []

제한사항

• 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$

---

🧊 파이썬 코드

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root : return None
        if val == root.val : return root #루트가 값이 같으면 그 트리 반환
        tree = self.searchBST(root.left, val)
        return self.searchBST(root.right, val) if tree == None else tree

저는 DFS로 풀었습니다.

🍹 다른사람 코드

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None or root.val == val: 
            return root # Return that node.
        return self.searchBST(root.left,val) if root.val > val else self.searchBST(root.right,val) 

로직은 비슷해보이지만 더 코드가 더 간결합니다.

🍸 또다른사람 코드

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        while root:
            if root.val==val:
                return root
            if root.val>val:
                root=root.left
            else:
                root=root.right
        return None

이건 재귀를 사용하지 않는 코드입니다.
근데 속도는 비슷하게 측정되네요.