이진 검색 트리가 주어지면 주어진 이진 검색에서 최소값을 가진 노드를 찾는 알고리즘을 작성합니다. 나무.
차례
예
입력
산출
5
순진한 접근
간단한 접근 방식은 트리 순회를 수행하고 모든 노드 중에서 최소값을 가진 노드를 찾는 것입니다. 이 방법은 이진 검색 트리뿐만 아니라 모든 일반 트리에도 유효합니다.
우리가 레벨 순서 순회 최소값을 찾으십시오.
- 루트가 null이면 최소값이 없으면 무한대를 반환합니다.
- 초기화 최소값은 무한합니다.
- 큐를 만들고 루트를 푸시합니다. 대기열이 비어 있지 않을 때 4 단계를 반복합니다.
- 큐에서 노드를 제거하고 최소값을 최소값의 최소값으로 업데이트하고 현재 노드의 값을 업데이트합니다. 현재 노드의 자식을 큐로 푸시합니다.
- 최소값을 반환합니다.
시간 복잡성 = 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
최적의 접근 방식
주어진 이진 트리는 이진 검색 트리입니다. 이진 검색 트리에는 노드보다 작은 모든 노드가 왼쪽 하위 트리에 있고이 노드보다 큰 모든 노드가 오른쪽 하위 트리에 존재한다는 특별한 속성이 있습니다.
이 속성을 사용하면 최소값을 가진 노드가 트리의 가장 왼쪽 노드로 존재한다고 말할 수 있습니다.
- 루트가 null이면 최소값이 없으며 무한을 반환합니다.
- 그렇지 않으면 임시를 루트로 초기화하십시오. temp의 왼쪽 노드가 null이 아닌 동안 3 단계를 반복합니다.
- temp를 temp의 왼쪽으로 만듭니다.
- 이 시점에서 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
