💛 오늘의 학습 키워드

[이진탐색트리] 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.

제한 조건

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

입출력 예

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

💬 내 풀이

public class day13 {

    public static void main(String[] args) {
    }

    public TreeNode searchBST(TreeNode root, int val){

        if(root == null) { 
        	return null;
        }

        if(root.val == val) {
            return root;
        }

        if(root.val > val) {
            return searchBST(root.left, val);
        }else {
            return searchBST(root.right, val);
        }
    }
}

💻 내 접근 방법

1. left, right 값은 val의 자식노드의 값이고, 이진 탐색 트리는 left 값이 rigth 값보다 작다는 것을 유념해두고 시작해야한다.
2. 만약 root 값이 null 인 경우 null을 return한다.
3. 찾고자하는 val 값이 root의 노드값(=root.val) 값과 같으면 root 를 return 한다.
4. 찾고자 하는 val 값 보다 root의 노드값이 작으면 다시 root 의 left 값을 탐색하고, 반대의 경우 right 값을 탐색하는 것을 반복한다.

💦 회고

열심히 작성했는데 왜 날라갔지ㅠㅠㅠ
if문 작성하고 {} 중괄호는 기본적으로 항상 써주자.
추가로 이 코드를 재귀방식이 아닌 stack으로 구현할 수 있다.

참고
https://st-lab.tistory.com/300