700. Search in a Binary Search Tree

Search in a Binary Search Tree - LeetCode

 

주어진 이진 탐색 트리 (BST)의 루트와 정수 val이 주어집니다.
BST에서 val과 값이 일치하는 노드를 찾아 해당 노드를 루트로 하는 서브 트리를 반환하거나, 그러한 노드가 존재하지 않는 경우 null을 반환하세요.

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

문제 요약:

주어진 이진 탐색 트리 (BST)에서 val과 값이 일치하는 노드를 찾아 해당 노드를 루트로 하는 서브 트리를 반환하거나, 그러한 노드가 존재하지 않는 경우 null을 반환하세요.

풀이과정:

1. 주어진 BST를 루트부터 탐색합니다.
2. 현재 노드의 값이 val과 같으면 해당 노드와 그 하위 서브 트리를 반환합니다.
3. 현재 노드의 값이 val보다 작으면 오른쪽 서브 트리에서 탐색을 계속합니다.
4. 현재 노드의 값이 val보다 크면 왼쪽 서브 트리에서 탐색을 계속합니다.
5. 탐색이 끝나고 val을 찾지 못하면 null을 반환합니다.

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null || root.val == val) return root;
        
        if(val < root.val){
            return searchBST(root.left, val);
        }else if(val > root.val) {
            return searchBST(root.right, val);
        }else{
            return null;
        }
    }
}