Um das größte Element kleiner als K in einem BST zu finden

Bei einem binären Suchbaum und einer Ganzzahl K möchte ich das größte Element kleiner als K finden.

Im unteren Baum,

for K = 13, result = 12
for K = 10, result = 8
for K = 1 (or) 2, result = -1

      10

  5       12

2   8   11  14

Ich habe die folgende Logik ausprobiert. Aber gibt es einen besseren Weg, dies zu tun?

int findNum(node* node, int K)
{
        if(node == NULL)
        {
                return -1;
        }
        else if(K <= node->data)
        {
                return findNum(node->left,K);
        }
        else if(K > node->data)
        {
                int t = findNum(node->right,K);
                return t > node->data ? t : node->data;
        }

        return -1;
}

Das ist O(log n), was das Minimum ist. Sie können jedoch die Effizienz verbessern (was diesen Interviewern anscheinend am wichtigsten ist) und die Möglichkeit eines Stapelüberlaufs (Tada!) Ausschließen, indem Sie die Schwanzrekursion eliminieren und dies in eine Schleife verwandeln. Außerdem funktioniert Ihr Code nicht, wenn der Baum negative Zahlen enthält … wenn Sie meinen nicht negativ Ganzzahlen, das sollten Sie sagen, aber wenn der Interviewer nur “Ganzzahlen” gesagt hat, brauchen Sie etwas anderen Code und eine andere API. (Sie könnten dieselbe Funktionssignatur beibehalten, aber bei einem Fehler K anstelle von -1 zurückgeben.)

Übrigens, da dies eine Interviewfrage ist, würde die Implementierung durch Aufrufen einer Bibliotheksfunktion den meisten Interviewern sagen, dass Sie ein Klugscheißer sind oder den Punkt verfehlen oder nicht wissen, wie sie es lösen sollen. Spielen Sie nicht mit solchen Dingen herum, sondern arbeiten Sie einfach daran, was der Interviewer will.

Hier ist eine Implementierung:

// Return the greatest int < K in tree, or K if none.
int findNum (Node* tree, int K)
{
    int val = K;

    while( tree )
        if( tree->data >= K )
            tree = tree->left;
        else{
            val = tree->data; 
            tree = tree->right;
        }

    return val;
}

Ich denke, die Idee hier ist, den letzten Knoten aufzuzeichnen, nach dem Sie zum rechten Teilbaum wechseln. Daher wird der Code (wurde aktualisiert)

int findNum (Node *node, int K)
{
    Node* last_right_move = NULL;

    while (node)
    {
        if (K<=node->data)
            node = node->left;
        else
        {
            last_right_move = node;
            node = node->right;
        }
    }

    if (last_right_move)
        return last_right_move->data;
    else
        return NOT_FOUND;  // defined previously. (-1 may conflict with negative number)
}

Ich glaube an die Verwendung von Standard-Bibliothekseinrichtungen. So nutzt meine Lösung std::set. 🙂

int largest_num_smaller_than(std::set<int> const& set, int num)
{
    std::set<int>::const_iterator lb(set.lower_bound(num));
    return lb == set.begin() ? -1 : *--lb;
}

Ich schlage vor, dass Sie den Code in Ihrer lokalen Implementierung von durchgehen set::upper_bound zur Führung. Dies ist nicht die Lösung für Ihr genaues Problem, aber sehr nah dran.

Im Allgemeinen müssen die meisten dieser Probleme im wirklichen Leben nicht in Ihrem eigenen Code gelöst werden. STL kann viele allgemeine Aufgaben für Sie erledigen. Es ist natürlich nützlich zu wissen, wie man sie löst, daher der Test.

Was die erste Antwort sagte, und hier ist die Logik dahinter, warum es nicht besser als O (log n) werden kann. Sie suchen nach der größten Zahl kleiner als K. Dies kommt dem Aufruf von BST-search/get ziemlich nahe.

Obwohl Ihr ursprünglicher Algorithmus ziemlich gut aussieht, denke ich, dass dies schneller wäre:

    int findNum (node root, int K) {
        if(root == null) return -1;

        if(K > root.val) { 
           if(root.right != null) return findNum(root.right, K);               
           else return root.val; 
        }

        return findNum(root.left, K); //look in left subtree

    }