이진 검색 트리에서 최소값을 가진 노드 찾기


난이도 중급
자주 묻는 질문 아마존 블룸버그 Microsoft
이진 검색 트리 이진 트리 폭 우선 검색 나무

이진 검색 트리가 주어지면 주어진 이진 검색에서 최소값을 가진 노드를 찾는 알고리즘을 작성합니다. 나무.

입력

이진 검색 트리에서 최소값을 가진 노드 찾기

산출
5

순진한 접근

간단한 접근 방식은 트리 순회를 수행하고 모든 노드 중에서 최소값을 가진 노드를 찾는 것입니다. 이 방법은 이진 검색 트리뿐만 아니라 모든 일반 트리에도 유효합니다.
우리가 레벨 순서 순회 최소값을 찾으십시오.

  1. 루트가 null이면 최소값이 없으면 무한대를 반환합니다.
  2. 초기화 최소값은 무한합니다.
  3. 큐를 만들고 루트를 푸시합니다. 대기열이 비어 있지 않을 때 4 단계를 반복합니다.
  4. 큐에서 노드를 제거하고 최소값을 최소값의 최소값으로 업데이트하고 현재 노드의 값을 업데이트합니다. 현재 노드의 자식을 큐로 푸시합니다.
  5. 최소값을 반환합니다.

시간 복잡성 = O (N)
공간 복잡성 = O (N)
여기서 n은 주어진 BST의 총 노드 수입니다.

최소값이있는 노드 찾기를위한 JAVA 코드

import java.util.LinkedList;
import java.util.Queue;

public class FindTheNodeWithMinimumValueInABinarySearchTree {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static int minValue(Node root) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }

        // initialize min as infinite
        int min = Integer.MAX_VALUE;

        // do a level order traversal of the tree
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node curr = queue.poll();

            // update minimum
            min = Math.min(min, curr.data);

            // add children of curr to queue
            if (curr.left != null)
                queue.add(curr.left);
            if (curr.right != null)
                queue.add(curr.right);
        }

        return min;
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(25);
        root.left = new Node(18);
        root.right = new Node(30);
        root.left.left = new Node(5);
        root.right.left = new Node(27);
        root.right.right = new Node(33);
        root.left.left.right = new Node(11);

        System.out.println(minValue(root));
    }
}
5

최소값이있는 노드 찾기를위한 C ++ 코드

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

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
};

int minValue(Node *root) {
    if (root == NULL) {
        return INT_MAX;
    }
    
    // initialize min as infinite
    int min = INT_MAX;
    
    // do a level order traversal of the tree
    queue<Node*> q;
    q.push(root);
    
    while (!q.empty()) {
        Node *curr = q.front();
        q.pop();
        
        // update minimum
        min = std::min(min, curr->data);
        
        // add children of curr to queue
        if (curr->left != NULL)
            q.push(curr->left);
        if (curr->right != NULL)
            q.push(curr->right);
    }
    
    return min;
}

int main() {
    // Example Tree
    Node *root = new Node(25);
    root->left = new Node(18);
    root->right = new Node(30);
    root->left->left = new Node(5);
    root->right->left = new Node(27);
    root->right->right = new Node(33);
    root->left->left->right = new Node(11);

    cout<<minValue(root)<<endl;
    
    return 0;
}
5

최적의 접근 방식

주어진 이진 트리는 이진 검색 트리입니다. 이진 검색 트리에는 노드보다 작은 모든 노드가 왼쪽 하위 트리에 있고이 노드보다 큰 모든 노드가 오른쪽 하위 트리에 존재한다는 특별한 속성이 있습니다.
이 속성을 사용하면 최소값을 가진 노드가 트리의 가장 왼쪽 노드로 존재한다고 말할 수 있습니다.

  1. 루트가 null이면 최소값이 없으며 무한을 반환합니다.
  2. 그렇지 않으면 임시를 루트로 초기화하십시오. temp의 왼쪽 노드가 null이 아닌 동안 3 단계를 반복합니다.
  3. temp를 temp의 왼쪽으로 만듭니다.
  4. 이 시점에서 temp는 가장 왼쪽 노드, 즉 최소값을 가진 노드를 가리 킵니다. 임시 데이터를 반환합니다.

시간 복잡성 = 오)
공간 복잡성 = O (1)
여기서 h는 주어진 이진 검색 트리의 높이이며, 최악의 경우 h는 n (노드 수)과 같습니다.

최소값이있는 노드 찾기를위한 JAVA 코드

public class FindTheNodeWithMinimumValueInABinarySearchTree {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static int minValue(Node root) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }

        // initialize temp as root
        Node temp = root;
        // go to the left most node
        while (temp.left != null) {
            temp = temp.left;
        }

        // return value of left most node
        return temp.data;
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(25);
        root.left = new Node(18);
        root.right = new Node(30);
        root.left.left = new Node(5);
        root.right.left = new Node(27);
        root.right.right = new Node(33);
        root.left.left.right = new Node(11);

        System.out.println(minValue(root));
    }
}
5

최소값이있는 노드 찾기를위한 C ++ 코드

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

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
};

int minValue(Node *root) {
    if (root == NULL) {
        return INT_MAX;
    }
    
    // initialize temp as root
    Node *temp = root;
    // go to the left most node
    while (temp->left != NULL) {
        temp = temp->left;
    }
    
    // return value of left most node
    return temp->data;
}

int main() {
    // Example Tree
    Node *root = new Node(25);
    root->left = new Node(18);
    root->right = new Node(30);
    root->left->left = new Node(5);
    root->right->left = new Node(27);
    root->right->right = new Node(33);
    root->left->left->right = new Node(11);

    cout<<minValue(root)<<endl;
    
    return 0;
}
5

참조