솔루션 개발:

질문

이 기사에서는 Leetcode의 '700. 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.

Example:

Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]

질문 설명

이 질문의 등급은 쉬움입니다. 대부분 정확합니다. 그러나 이것은 이진 검색 트리에 대한 기본적인 이해가 있는 경우에만 쉽습니다. 그렇지 않다면 이 질문으로 인해 곤란한 하루를 보내게 될 것입니다.

우리가 요구하는 것은 BST에서 숫자를 찾는 것입니다. 번호가 BST에 없으면 null를 반환합니다. 숫자가 BST에 있는 경우 해당 숫자를 루트로 하는 하위 트리를 반환합니다.

권장 지식

Binary Trees

Binary Search Trees

Depth First Search Recursive

Divide and Conquer

우리는 무엇을 알고 있습니까?

이진 검색 트리가 있고 값을 검색해야 합니다

.

이진 검색 트리의 속성을 사용하여 O(log n)에서 이를 수행할 수 있습니다. Divide and Conquer 알고리즘으로 검색할 수 있습니다.

어떻게 할 것인가:

모든 node로 이동하여 주어진 값이 우리가 찾아야 하는 값보다 큰지 작은지 묻습니다.

먼저 이 작업을 재귀적으로 수행하겠습니다. 즉, 가능한 모든 결과에 대해 node마다 확인해야 합니다.

먼저 묻습니다. 이것은 node 잎사귀node입니까? 이 경우, 우리는 우리가 찾는 것을 찾지 못한 목록의 끝에 도달했습니다.

그런 다음 '현재node가 우리가 찾고 있던 것입니까?'라고 묻습니다. 값을 비교하여 이를 수행합니다. 동일하면 찾았으므로 node 를 반환합니다.

이제 찾지 못한 경우 다음에 가야 할 곳을 알아야 합니다. 왼쪽으로 가야 합니까 아니면 오른쪽으로 가야 합니까? 현재 값이 우리가 찾고 있는 값보다 크면 왼쪽 값이 항상 현재 값보다 작기 때문에 왼쪽으로 이동하므로 값이 왼쪽에 있게 됩니다. 동일한 논리가 오른쪽node에 적용됩니다. 여기서 현재 값이 우리가 찾고 있는 값보다 작으면 더 큰 숫자가 있는 곳임을 알기 때문에 오른쪽으로 이동합니다.

목록의 끝에 도달하거나 찾고 있는 항목에 도달할 때까지 이 작업을 반복합니다.

빅오 표기법:

시간 복잡도: O(log n) | 여기서 n은 node s의 수이며 이동할 때마다 검색 트리를 반으로 나누기 때문에 트리에 로그가 있습니다. 대수입니다. 분할 정복 알고리즘을 사용하고 있습니다

.

공간 복잡도: O(1) | 추가 공간을 할당하지 않기 때문입니다.

리트코드 결과:

제출 링크 참조:

런타임: 72ms, 이진 검색 트리에서 검색을 위한 JavaScript 온라인 제출의 97.71%보다 빠름

해결책

var searchBST = function (root, val) {

    // We have reached a leaf node
    // This mean's we never found the
    // node we was looking for.
    if (!root) {
        return null;
    }

    // We found the node we're looking for
    // Return it.
    if (root.val === val) {
        return root;
    }

    // The 2 parts below only make sense if you understand
    // Binary Search Trees. It helps if you understand divide and conquer algorithms.
    // Like Binary search.

    // So we know the value we're looking for
    // if greater than the current node, thus
    // the node we're looking for is somewhere on the right tree
    if (val > root.val) {
        return searchBST(root.right, val);
    }

    // So the value we're searching for is less than the current node
    // which means the node we're looking for exists somewhere on
    // the left side.
    if (val < root.val) {
        return searchBST(root.left, val);
    }
};