이진 검색 트리 Leetcode 솔루션에서 검색

난이도 쉽게
자주 묻는 질문 Apple IBM
알고리즘 이진 검색 트리 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 48

이 문제에서 우리는 이진 검색 트리 및 정수. 주어진 정수와 같은 값을 가진 노드의 주소를 찾아야합니다. 확인을 위해이 노드가 루트 인 하위 트리의 사전 주문 순회를 인쇄해야합니다. 트리에 주어진 정수와 동일한 값이 없으면 다음을 반환해야합니다. NULL즉, 빈 나무.

예

     2
    
  /     \

1         3

             \

               4


Target Value = 3
3 4
     5

  /      \

1         10 


Target Value = 4
Empty BST

설명 # 1

BST에는 값이 3 인 노드가 포함되어 있으므로 하위 트리를 반환하고 사전 주문 순회를 인쇄합니다.

설명 # 2

BST는 값이 4 인 노드를 포함하지 않으므로 NULL을 반환하고 "Empty BST"를 인쇄합니다.

접근 (재귀)

이 경우 문제가 하위 문제에 어떻게 의존하는지 생각해 보겠습니다. 우리 함수가 발견되면 목표 값과 함께 노드의 주소를 반환한다고 가정 해 봅시다. 우리는 나무의 뿌리에서 시작합니다. 이 노드가 Null 이진 검색 트리의 끝에 도달 했으므로 대상 값이있는 노드가 없음이 분명합니다. 그래서 우리는 없는. 마찬가지로 노드 값이 목표 값과 같으면이 노드를 반환합니다. 그렇지 않으면 대상 값 노드가 왼쪽 (left) 하위 트리 또는 연락해주세요 현재 루트의 하위 트리. root.value와 target 값을 비교하여 방향 (왼쪽 또는 오른쪽)을 결정할 수 있습니다. 따라서 동일한 재귀 함수를 다음과 같이 호출합니다. 뿌리 as root.left or 루트.오른쪽.

이진 검색 트리 Leetcode 솔루션에서 검색핀

암호알고리즘

  1. 함수 만들기 searchBST () 반환 대상 주소
  2. If 뿌리 동일하다 null로 OR 뿌리 대상과 동일한 값을가집니다.
    • 루트 반환
  3. root.value가 목표 값보다 큰 경우 :
    1. 반환 searchBST (root.left, val)
  4. 반품 searchBST (root.right, val)
  5. 대상 노드의 사전 주문 순회 인쇄

이진 검색 트리 Leetcode 솔루션에서 검색 구현

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int val)
    {
        value = val;
        left = right = NULL;
    }
};

void preorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    cout << root->value << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
    return;
}

BSTNode* searchBST(BSTNode* root , int val)
{
    if(root == NULL)
        return root;
    if(val == root->value)
        return root;
    if(val < root->value)
        return searchBST(root->left , val);
    return searchBST(root->right , val);
}

int main()
{
    BSTNode* root = new BSTNode(2);
    root->left = new BSTNode(1);
    root->right = new BSTNode(3);
    root->right->right = new BSTNode(4);
    int val = 3;
    BSTNode* targetNode = searchBST(root , val);
    if(targetNode == NULL)
    {
        cout << "Empty Tree" << '\n';
        return 0;
    }
    preorderTraversal(targetNode);
    return 0;
}

자바 프로그램

class BSTNode
{
    int value;
    BSTNode left , right;
    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class search_in_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(2);
        root.left = new BSTNode(1);
        root.right = new BSTNode(3);
        root.right.right = new BSTNode(4);
        int val = 3;
        BSTNode targetNode = searchBST(root , val);
        if(targetNode == null)
        {
            System.out.println("Empty Tree");
            System.exit(0);
        }
        preorderTraversal(targetNode);
    }

    static BSTNode searchBST(BSTNode root , int val)
    {
        if(root == null)
            return root;
        if(val == root.value)
            return root;
        if(val < root.value)
            return searchBST(root.left , val);
        return searchBST(root.right , val);
    }

    static void preorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        System.out.print(root.value + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return;
    }
}
3 4

이진 검색 트리 Leetcode 솔루션에서 검색의 복잡성 분석

시간 복잡성

O (H), H = logN = 평균 사례에서 BST의 높이 O (N), N = 최악의 경우 BST의 크기. BST가 치우 쳤을 때 발생하는 최악의 경우 트리를 한 번 횡단합니다.

공간 복잡성

오) 평균적으로 모든 노드를 순회하기 위해 재귀 호출을 사용합니다. 의 위에) 최악의 경우. 한 가지 중요한 점은 일부 컴파일러가 꼬리 재귀 그런 경우 공간 복잡성은 O (1).

접근 (반복)

위의 접근 방식과 유사하게 현재 노드에 대상 값이 없으면 왼쪽 또는 오른쪽 하위 트리로 이동할 수 있습니다. 다음을 할당하여 반복적으로 수행 할 수 있습니다. 루트 = root.left or 루트 = root.right 루트가 될 때까지 모든 반복에서 없는. 어떤 반복에서도 root의 값이 목표 값과 같다는 것을 발견하면 해당 root를 반환합니다. 그렇지 않으면 우리는 없는.

암호알고리즘

  1. 유사한 기능 만들기 searchBST () 대상 노드의 주소를 반환
  2. DaVinci에는 뿌리 is 지원 없는:
    • if 루트 값 목표 값과 같음
      • 반환 뿌리
    • if 루트.발 is 큰 목표 값보다
      • 다음과 같이 오른쪽 하위 트리로 이동합니다. 루트 = root.right
    • 그렇지 않으면
      • 다음과 같이 왼쪽 하위 트리로 이동합니다. 루트 = root.left
  3. 반품 null로
  4. 대상 노드의 사전 주문 순회 인쇄

이진 검색 트리 Leetcode 솔루션에서 검색 구현

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int val)
    {
        value = val;
        left = right = NULL;
    }
};

void preorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    cout << root->value << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
    return;
}

BSTNode* searchBST(BSTNode* root , int val)
{
    while(root != NULL)
    {
        if(root->value == val)
            return root;
        if(root->value > val)
            root = root->left;
        else
            root = root->right;
    }
    return NULL;
}

int main()
{
    BSTNode* root = new BSTNode(2);
    root->left = new BSTNode(1);
    root->right = new BSTNode(3);
    root->right->right = new BSTNode(4);
    int val = 3;
    BSTNode* targetNode = searchBST(root , val);
    if(targetNode == NULL)
    {
        cout << "Empty Tree" << '\n';
        return 0;
    }
    preorderTraversal(targetNode);
    return 0;
}

자바 프로그램

class BSTNode
{
    int value;
    BSTNode left , right;
    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class search_in_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(2);
        root.left = new BSTNode(1);
        root.right = new BSTNode(3);
        root.right.right = new BSTNode(4);
        int val = 3;
        BSTNode targetNode = searchBST(root , val);
        if(targetNode == null)
        {
            System.out.println("Empty Tree");
            System.exit(0);
        }
        preorderTraversal(targetNode);
    }

    static BSTNode searchBST(BSTNode root , int val)
    {
        while(root != null)
        {
            if(root.value == val)
                return root;
            if(root.value > val)
                root = root.left;
            else
                root = root.right;
        }
        return null;
    }

    static void preorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        System.out.print(root.value + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return;
    }
}

3 4

이진 검색 트리 Leetcode 솔루션에서 검색의 복잡성 분석

시간 복잡성

O (H = logN) 평균적인 경우 의 위에) 최악의 경우 (비뚤어진 BST), 위의 접근 방식과 동일합니다.

공간 복잡성

O (1) 일정한 메모리 공간 만 사용하기 때문입니다.

코멘트를 남겨

Translate »
1