二分探索木で最小値のノードを見つけます


難易度 ミディアム
よく聞かれる Amazon (アマゾン) ブルームバーグ マイクロソフト
二分探索木 二分木 幅優先探索 キュー

二分探索木が与えられた場合、与えられた二分探索で最小値を持つノードを見つけるアルゴリズムを記述します ツリー.

入力

二分探索木で最小値のノードを見つけます

出力
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をrootとして初期化します。 tempの左側のノードがnullでないときに、手順3を繰り返します。
  3. tempをtempの左と等しくします。
  4. この時点で、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

リファレンス