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.
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의 오른쪽 방향으로 탐색
현재 노드의 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)
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