LeetCode 솔루션 분류

700. Search in a Binary Search Tree

컨텐츠 정보

본문

[ Leetcode 시즌 3 ] 2022년도 4월 13일 문제 입니다.


[Easy] 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 <= 107
  • root is a binary search tree.
  • 1 <= val <= 107
 

관련자료

댓글 3

mingki님의 댓글

  • 익명
  • 작성일
C++
Runtime: 60 ms, faster than 39.28% of C++ online submissions for Search in a Binary Search Tree.
Memory Usage: 34.8 MB, less than 66.88% of C++ online submissions for Search in a Binary Search Tree.
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        for (; root && root->val != val; root = val < root->val ? root->left : root->right)
            ;
        return root;
    }
};

Coffee님의 댓글

  • 익명
  • 작성일
재귀적 접근, node가 null이거나 val을 못찾으면 null값 return.
현재 노드의 val이 target val보다 작으면, root의 왼쪽 방향으로 탐색
현재 노드의 val이 target val보다 크면, root의 오른쪽 방향으로 탐색
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {     
        if(root == null || val == root.val){
            return root;
        }
        return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
        
    }
}

coderoncruise님의 댓글

  • 익명
  • 작성일
Intuition
Binary Search Tree:
each node > left nodes
each node < right nodes
https://www.youtube.com/watch?v=Lr2oxJlnLMM

Approach 1: Recursion
TC: O(H) where H is a tree height.
SC: O(H) to keep the recursion stack

Approach 2: Iteration
TC: O(H)
SC: O(1)

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

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        cur = root
        
        while cur and cur.val != val:
            
            if val < cur.val:
                cur = cur.left
            else:
                cur = cur.right
        
        
        return cur
LeetCode 솔루션 357 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0