LeetCode 700(Search in a Binary Search Tree, java)

0. 문제

https://leetcode.com/problems/search-in-a-binary-search-tree/

Search in a Binary Search Tree - LeetCode

 

1. 문제 설명

- 문제에서 이진 탐색 트리(= root)와 정수(= val)가 주어진다.

- 이진탐색트리를 탐색하는 과정에서 어떤 노드의 value가 주어진 정수(= val)와 동일한 경우를 찾는다.

- 해당 노드의 모든 자식 노드를 반환하는 것이 문제의 핵심이다. 

2. 문제 해설

a) 첫 번째 접근

- 탐색을 진행하기전에 이진 탐색 트리(BST)의 특성을 이해해야 한다.

- 자식 노드의 value > 부모 노드의 value인 경우, 자식 노드는 부모 노드의 우측 자식 노드가 된다.

- 반대로 자식 노드의 value < 부모 노드의 value인 경우, 자식 노드는 부모 노드의 좌측 자식 노드가 된다.

- 이를 염두에 두고 탐색을 진행해야 한다.

 

b) 두 번째 접근

- 이진 탐색 트리를 탐색한다. 

- 그 과정에서 노드의 value가 문제에서 주어진 정수(= val) 보다 크다면, root.left를 탐색한다.

- 반대의 경우, root.right를 탐색한다.

 

- 이를 그대로 재귀 함수로 구현하면 된다.

- 다음 코드를 보면서 이해해보자.  

 

3. 정답 코드

class Solution {
    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);
        }
    }
}