[99클럽 코테 스터디] 13일차 TIL 이분탐색

 

 

오늘의 문제는 LeetCode

 

Search in a Binary Search Tree

 

 

문제

 

 

 

문제 설명 

 

이진 탐색 트리와 루트가 주어지면 노드의 값이 val과 동일한 노드를 찾아야 하는 문제입니다. 만약 val과 같은 값의 노드가 없다면 null을 반환하고, 있다면 해당 노드와 루트가 있는 하위 트리를 반환하면 됩니다. 

 

문제 풀이 시간

권장 풀이 시간은 30분이었고, 저는 33분이 걸렸습니다.

 

 

 

문제 접근 방식

이진탐색트리에서 주어진 값을 찾으려면 우선 while문을 사용해 더 이상 탐색할 노드가 없을 때까지 탐색을 계속 합니다. 그 다음 만약 주어진 값과 같은 노드 값을 찾는다면 해당 노드를 루트로 하는 서브트리를 반환합니다.

만약 찾고자 하는 값이 현재 노드의 값보다 작은 경우 이진탐색트리의 특성 상 왼쪽 서브트리에 해당 값이 있을 수 있으므로 왼쪽 자식 노드로 변경해 탐색을 계속합니다. 찾고자 하는 값이 현재 노드 값보다 큰 경우엔 반대로 오른쪽 서브트리에 해당 값이 있을 수 있으므로 오른쪽 자식 노드로 변경해 탐색을 계속합니다. 반복문을 통한 탐색이 끝났으면 찾고자 하는 값을 찾지 못한 것이므로 null 값을 반환합니다. 

 

 

 

문제 풀이

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null) {
            if (val == root.val) {
                return root;
            } else if (val < root.val) {
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return null;
    }
}

 

 

이진탐색트리의 특성 알아보기 

이진 탐색 트리는 이진 트리 기반의 탐색을 위한 자료구조로, 이진 트리를 기반으로 하기 때문에 모든 노드가 최대 2개의 자식 노드를 갖습니다. 모든 노드의 값은 유일한 값이며 루트 노드를 기준으로 왼쪽엔 작은 값이 오른쪽엔 큰 값이 위치합니다. 

 

 

 

return root

return root는 해당 노드를 루트로 하는 서브트리를 반환하는 코드입니다. 이진탐색트리에서 특정 노드를 찾을 때, 그 노드와 함께 해당 노드를 루트로 하는 서브트리를 반환합니다. 

 

 

노드 구성요소 알아보기 

 

root.val : val은 키 값이지만 해당 코드에선 현재 노드의 값을 의미합니다. 이 값은 노드를 식별하는데 사용됩니다. 

 

root.left : left는 현재 노드의 왼쪽 자식 노드를 가리키는 참조입니다. 이진탐색트리 규칙에 따라 왼쪽 자식 노드의 값은 현재 노드 보다 작은  값입니다. 만약 root.left가 null이 아니라면 현재 노드의 왼쪽에 또 다른 노드가 있다는 것을 의미합니다. 찾고자 하는 값이 현재 노드의 값보다 작은 경우, 왼쪽 자식 노드로 이동해 탐색을 계속하게 됩니다. 

 

root.right : right는 현재 노드의 오른쪽 자식 노드를 가리키는 참조입니다. 이진탐색트리 규칙에 따라 오른쪽 자식 노드의 값은 현재 노드 보다 큰 값입니다. 만약 root.right가 null이 아니라면 현재 노드의 오른쪽에 다른 노드가 있다는 것을 의미합니다. 찾고자 하는 값이 현재 노드의 값보다 큰 경우, 오른쪽 자식 노드로 이동해 탐색을 계속하게 됩니다. 

 

 

 

 

 

이렇게 오늘 13일차 TIL을 작성해 보았습니다.