1 | 오늘의 문제

1. 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.

2. 이진탐색트리

• 이진트리의 한 종류
• 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
• 기본적으로 중복된 값을 허용하지 않는다. 허용하기 위해서는 규칙 등이 필요하다.

1. 왼쪽 혹은 오른쪽에 중복된 값 배치
2. 노드에서 카운터 유지

• 탐색: 찾으려는 값을 int val이라고 할 때, val가 노드보다 작으면 왼쪽, 크면 오른쪽으로 이동한다.
• 삽입: 탐색을 거쳐 적절한 위치를 찾는다.
• 삭제

중요한 것은 탐색 시 재귀적으로 시행할 수 있다는 것!

3. 풀이

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null) {  //1. null
            return null;
        }  
        if (root.val == val) { //2. equal
            return root;
        }  
        
        if (root.val < val) { //3. Greater
            return searchBST(root.right, val);
        }
        
        return searchBST(root.left, val); //4.Less
    }
}

재귀적으로 시행한다!!!

참고: 이진탐색트리 정의

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */