Finden Sie das k-te kleinste Element in einem binären Suchbaum auf optimale Weise

112

Ich muss das k-te kleinste Element im binären Suchbaum finden, ohne eine statische / globale Variable zu verwenden. Wie kann man es effizient erreichen? Die Lösung, die ich im Kopf habe, ist die Operation in O (n), der schlimmste Fall, da ich vorhabe, den gesamten Baum in der Reihenfolge zu durchlaufen. Aber tief im Inneren habe ich das Gefühl, dass ich die BST-Eigenschaft hier nicht benutze. Ist meine angenommene Lösung korrekt oder gibt es eine bessere?

Prahler
quelle
7
Ist der Baum ausgeglichen?
Kennytm
Es ist nicht. Aber wenn es ausgeglichen wäre, gibt es einen optimalen Weg?
Bragboy
1
Wenn Sie nach "Bestellstatistik" suchen, finden Sie, was Sie brauchen.
RAL
Ich habe das Gefühl, dass die meisten der folgenden Antworten, obwohl sie korrekt sind, insofern schummeln, als sie eine globale Variable verwenden (ob es sich um eine Referenz auf eine Ganzzahl handelt oder um eine Variable, die dekrementiert und zurückgegeben wird). Wenn absolut nichts davon erlaubt ist, würde ich die Rekursion verwenden, ohne dass Referenzen übergeben werden.
Henley Chiu

Antworten:

170

Hier ist nur ein Überblick über die Idee:

In einer BST Tenthält der linke Teilbaum des Knotens nur Elemente, die kleiner als der darin gespeicherte Wert sind T. Wenn kes kleiner als die Anzahl der Elemente im linken Teilbaum ist, muss das kkleinste Element zum linken Teilbaum gehören. Wenn kes größer ist, befindet sich das kkleinste Element im rechten Teilbaum.

Wir können die BST erweitern, damit jeder Knoten die Anzahl der Elemente in seinem linken Teilbaum speichert (vorausgesetzt, der linke Teilbaum eines bestimmten Knotens enthält diesen Knoten). Mit dieser Information ist es einfach, den Baum zu durchlaufen, indem wiederholt nach der Anzahl der Elemente im linken Teilbaum gefragt wird, um zu entscheiden, ob in den linken oder rechten Teilbaum zurückgegriffen werden soll.

Nehmen wir nun an, wir befinden uns am Knoten T:

  1. Wenn k == num_elements (linker Teilbaum von T) ist , ist die gesuchte Antwort der Wert im Knoten T.
  2. Wenn k> num_elements (linker Teilbaum von T) ist , können wir natürlich den linken Teilbaum ignorieren, da diese Elemente auch kleiner als der kkleinste sind. Wir reduzieren das Problem also darauf, das k - num_elements(left subtree of T)kleinste Element des richtigen Teilbaums zu finden.
  3. Wenn k <num_elements (linker Teilbaum von T) ist , befindet sich der kkleinste Teil irgendwo im linken Teilbaum, sodass wir das Problem darauf reduzieren, das kkleinste Element im linken Teilbaum zu finden.

Komplexitätsanalyse:

Dies braucht O(depth of node)Zeit, was O(log n)im schlimmsten Fall bei einer ausgeglichenen BST oder O(log n)im Durchschnitt bei einer zufälligen BST der Fall ist .

Ein BST erfordert O(n)Speicherplatz, und ein anderer benötigt O(n)zum Speichern der Informationen über die Anzahl der Elemente. Alle BST-Operationen benötigen O(depth of node)Zeit, und es dauert O(depth of node)zusätzliche Zeit, um die Informationen zur "Anzahl der Elemente" zum Einfügen, Löschen oder Drehen von Knoten zu verwalten. Durch das Speichern von Informationen über die Anzahl der Elemente im linken Teilbaum bleibt daher die räumliche und zeitliche Komplexität einer BST erhalten.

IVlad
quelle
59
Um das N-kleinste Element zu finden, müssen Sie nur die Größe des linken Unterbaums speichern. Sie würden die Größe des rechten Unterbaums verwenden, wenn Sie auch den n-ten größten Gegenstand finden möchten. Tatsächlich können Sie dies jedoch kostengünstiger gestalten: Speichern Sie die Gesamtgröße des Baums in der Wurzel und die Größe des linken Unterbaums. Wenn Sie die Größe des rechten Teilbaums benötigen, können Sie die Größe des linken von der Gesamtgröße abziehen.
Jerry Coffin
37
Eine solche erweiterte BST wird als "Auftragsstatistikbaum" bezeichnet.
Daniel
10
@Ivlad: in Schritt 2: Ich denke, "k - num_elements" sollte "k - num_elements -1" sein, da Sie auch das Root-Element einschließen müssen.
Understack
1
@understack - nicht, wenn Sie annehmen, dass die Wurzel Teil des Teilbaums ist.
IVlad
16
Wenn der Baum kein Feld enthält, das die "Anzahl der Elemente in seinem linken und rechten Teilbaum" enthält, lautet die Methode BigO (n), da Sie an jedem Knoten den rechten oder linken Teilbaum durchlaufen müssen, um dies zu tun Berechnen Sie den k-Index des aktuellen Knotens.
Robert S. Barnes
68

Eine einfachere Lösung wäre, eine Inorder Traversal durchzuführen und das aktuell zu druckende Element zu verfolgen (ohne es zu drucken). Wenn wir k erreichen, drucken Sie das Element und überspringen Sie den Rest der Baumdurchquerung.

void findK(Node* p, int* k) {
  if(!p || k < 0) return;
  findK(p->left, k);
  --k;
  if(k == 0) { 
    print p->data;
    return;  
  } 
  findK(p->right, k); 
}
prasadvk
quelle
1
+1: Die Idee ist in die richtige Richtung, aber einige lose Enden müssen möglicherweise festgezogen werden. siehe stackoverflow.com/a/23069077/278326
Arun
1
Ich mag diese Lösung, da BST bereits bestellt ist, sollte eine Durchquerung ausreichen.
Merlin
3
Wenn n nahe an der Gesamtzahl der Knoten in diesem Baum liegt, benötigt Ihr Algorithmus O (n) Zeit, um fertig zu werden, was für die ausgewählte Antwort-O (log n) schlecht ist
Spark8006
13
public int ReturnKthSmallestElement1(int k)
    {
        Node node = Root;

        int count = k;

        int sizeOfLeftSubtree = 0;

        while(node != null)
        {

            sizeOfLeftSubtree = node.SizeOfLeftSubtree();

            if (sizeOfLeftSubtree + 1 == count)
                return node.Value;
            else if (sizeOfLeftSubtree < count)
            {
                node = node.Right;
                count -= sizeOfLeftSubtree+1;
            }
            else
            {
                node = node.Left;
            }
        }

        return -1;
    }

Dies ist meine Implementierung in C #, basierend auf dem obigen Algorithmus. Ich dachte nur, ich würde es veröffentlichen, damit die Leute besser verstehen können, dass es für mich funktioniert

Danke IVlad

Abs
quelle
11

Eine einfachere Lösung wäre, eine Inorder Traversal durchzuführen und das aktuell zu druckende Element mit einem Zähler k zu verfolgen. Wenn wir k erreichen, drucken Sie das Element. Die Laufzeit ist O (n). Denken Sie daran, dass der Funktionstyp nicht ungültig sein kann. Er muss nach jedem rekursiven Aufruf seinen aktualisierten Wert von k zurückgeben. Eine bessere Lösung hierfür wäre eine erweiterte BST mit einem sortierten Positionswert an jedem Knoten.

public static int kthSmallest (Node pivot, int k){
    if(pivot == null )
        return k;   
    k = kthSmallest(pivot.left, k);
    k--;
    if(k == 0){
        System.out.println(pivot.value);
    }
    k = kthSmallest(pivot.right, k);
    return k;
}
Sumit Balani
quelle
Ich denke, Ihre Lösung ist in Bezug auf die Platzkomplexität besser als die erweiterte BST.
Zach
Die Suche hört auch dann nicht auf, wenn das k-te kleinste Element gefunden wurde.
Vineeth Chitteti
10

// eine Java-Version ohne Rekursion hinzufügen

public static <T> void find(TreeNode<T> node, int num){
    Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();

    TreeNode<T> current = node;
    int tmp = num;

    while(stack.size() > 0 || current!=null){
        if(current!= null){
            stack.add(current);
            current = current.getLeft();
        }else{
            current = stack.pop();
            tmp--;

            if(tmp == 0){
                System.out.println(current.getValue());
                return;
            }

            current = current.getRight();
        }
    }
}
Jiaji Li
quelle
Ich mag diese Lösung und die entsprechende rekursive. Ehrlich gesagt sind die meisten Antworten auf diese Frage zu verwirrend / komplex, um sie zu lesen.
Henley Chiu
Ich liebe diese Lösung! Klar und toll!
Rugal
Diese Lösung durchläuft den Baum "in der richtigen Reihenfolge" und verringert einen Zähler nach dem Besuch des Knotens, um später anzuhalten, wenn der Zähler gleich Null wird. Der schlimmste Fall liegt dann in der Größenordnung von O (n). Nicht der optimalste Vergleich mit @ IVlads rekursiven Lösungen, deren schlimmster Fall O (log n) ist
Jorge P.
4

Wenn Sie nur einen einfachen binären Suchbaum haben, können Sie nur mit dem kleinsten beginnen und nach oben gehen, um den richtigen Knoten zu finden.

Wenn Sie dies sehr oft tun, können Sie jedem Knoten ein Attribut hinzufügen, das angibt, wie viele Knoten sich in seinem linken Unterbaum befinden. Auf diese Weise können Sie den Baum direkt zum richtigen Knoten absteigen.

Jerry Sarg
quelle
4

Rekursiver In-Order-Walk mit einem Zähler

Time Complexity: O( N ), N is the number of nodes
Space Complexity: O( 1 ), excluding the function call stack

Die Idee ähnelt der @ prasadvk-Lösung, weist jedoch einige Mängel auf (siehe Anmerkungen unten). Daher veröffentliche ich diese als separate Antwort.

// Private Helper Macro
#define testAndReturn( k, counter, result )                         \
    do { if( (counter == k) && (result == -1) ) {                   \
        result = pn->key_;                                          \
        return;                                                     \
    } } while( 0 )

// Private Helper Function
static void findKthSmallest(
    BstNode const * pn, int const k, int & counter, int & result ) {

    if( ! pn ) return;

    findKthSmallest( pn->left_, k, counter, result );
    testAndReturn( k, counter, result );

    counter += 1;
    testAndReturn( k, counter, result );

    findKthSmallest( pn->right_, k, counter, result );
    testAndReturn( k, counter, result );
}

// Public API function
void findKthSmallest( Bst const * pt, int const k ) {
    int counter = 0;
    int result = -1;        // -1 := not found
    findKthSmallest( pt->root_, k, counter, result );
    printf("%d-th element: element = %d\n", k, result );
}

Anmerkungen (und Unterschiede zur Lösung von @ prasadvk):

  1. if( counter == k )Der Test ist an drei Stellen erforderlich : (a) nach dem linken Teilbaum, (b) nach der Wurzel und (c) nach dem rechten Teilbaum. Dies soll sicherstellen, dass das k-te Element für alle Standorte erkannt wird , dh unabhängig von dem Teilbaum, in dem es sich befindet.

  2. if( result == -1 )Test erforderlich, um sicherzustellen, dass nur das Ergebniselement gedruckt wird. Andernfalls werden alle Elemente vom k-ten kleinsten bis zur Wurzel gedruckt.

Arun
quelle
Die zeitliche Komplexität für diese Lösung ist O(k + d), wo ddie maximale Tiefe des Baums ist. Daher wird eine globale Variable verwendet counter, die für diese Frage jedoch unzulässig ist.
Valentin Shergin
Hallo Arun, kannst du das bitte anhand eines Beispiels erklären. Ich verstehe das nicht besonders Ihren ersten Punkt.
Andy897
3

Für einen nicht ausgeglichenen Suchbaum wird O (n) benötigt .

Für einen ausgeglichenen Suchbaum wird im schlimmsten Fall O (k + log n ) benötigt, im amortisierten Sinne jedoch nur O (k) .

Die zusätzliche Ganzzahl für jeden Knoten haben und verwalten: Die Größe des Unterbaums gibt O (log n) Zeitkomplexität. Ein solcher ausgeglichener Suchbaum wird normalerweise als RankTree bezeichnet.

Im Allgemeinen gibt es Lösungen (basierend nicht auf Baum).

Grüße.

Slava
quelle
1

Dies funktioniert gut: status: ist das Array, das enthält, ob ein Element gefunden wird. k: ist das zu findende k-te Element. count: Verfolgt die Anzahl der Knoten, die während der Baumdurchquerung durchlaufen wurden.

int kth(struct tree* node, int* status, int k, int count)
{
    if (!node) return count;
    count = kth(node->lft, status, k, count);  
    if( status[1] ) return status[0];
    if (count == k) { 
        status[0] = node->val;
        status[1] = 1;
        return status[0];
    }
    count = kth(node->rgt, status, k, count+1);
    if( status[1] ) return status[0];
    return count;
}
Pranjal
quelle
1

Dies ist definitiv nicht die optimale Lösung für das Problem, aber es ist eine weitere mögliche Lösung, die einige Leute für interessant halten könnten:

/**
 * Treat the bst as a sorted list in descending order and find the element 
 * in position k.
 *
 * Time complexity BigO ( n^2 )
 *
 * 2n + sum( 1 * n/2 + 2 * n/4 + ... ( 2^n-1) * n/n ) = 
 * 2n + sigma a=1 to n ( (2^(a-1)) * n / 2^a ) = 2n + n(n-1)/4
 *
 * @param t The root of the binary search tree.
 * @param k The position of the element to find.
 * @return The value of the element at position k.
 */
public static int kElement2( Node t, int k ) {
    int treeSize = sizeOfTree( t );

    return kElement2( t, k, treeSize, 0 ).intValue();
}

/**
 * Find the value at position k in the bst by doing an in-order traversal 
 * of the tree and mapping the ascending order index to the descending order 
 * index.
 *
 *
 * @param t Root of the bst to search in.
 * @param k Index of the element being searched for.
 * @param treeSize Size of the entire bst.
 * @param count The number of node already visited.
 * @return Either the value of the kth node, or Double.POSITIVE_INFINITY if 
 *         not found in this sub-tree.
 */
private static Double kElement2( Node t, int k, int treeSize, int count ) {
    // Double.POSITIVE_INFINITY is a marker value indicating that the kth 
    // element wasn't found in this sub-tree.
    if ( t == null )
        return Double.POSITIVE_INFINITY;

    Double kea = kElement2( t.getLeftSon(), k, treeSize, count );

    if ( kea != Double.POSITIVE_INFINITY )
        return kea;

    // The index of the current node.
    count += 1 + sizeOfTree( t.getLeftSon() );

    // Given any index from the ascending in order traversal of the bst, 
    // treeSize + 1 - index gives the
    // corresponding index in the descending order list.
    if ( ( treeSize + 1 - count ) == k )
        return (double)t.getNumber();

    return kElement2( t.getRightSon(), k, treeSize, count );
}
Robert S. Barnes
quelle
1

Unterschrift:

Node * find(Node* tree, int *n, int k);

Anruf als:

*n = 0;
kthNode = find(root, n, k);

Definition:

Node * find ( Node * tree, int *n, int k)
{
   Node *temp = NULL;

   if (tree->left && *n<k)
      temp = find(tree->left, n, k);

   *n++;

   if(*n==k)
      temp = root;

   if (tree->right && *n<k)
      temp = find(tree->right, n, k);

   return temp;
}
Ziel
quelle
1

Na hier sind meine 2 Cent ...

int numBSTnodes(const Node* pNode){
     if(pNode == NULL) return 0;
     return (numBSTnodes(pNode->left)+numBSTnodes(pNode->right)+1);
}


//This function will find Kth smallest element
Node* findKthSmallestBSTelement(Node* root, int k){
     Node* pTrav = root;
     while(k > 0){
         int numNodes = numBSTnodes(pTrav->left);
         if(numNodes >= k){
              pTrav = pTrav->left;
         }
         else{
              //subtract left tree nodes and root count from 'k'
              k -= (numBSTnodes(pTrav->left) + 1);
              if(k == 0) return pTrav;
              pTrav = pTrav->right;
        }

        return NULL;
 }
Manish Shukla
quelle
0

Das ist was ich aber und es funktioniert. Es wird in o (log n) ausgeführt.

public static int FindkThSmallestElemet(Node root, int k)
    {
        int count = 0;
        Node current = root;

        while (current != null)
        {
            count++;
            current = current.left;
        }
        current = root;

        while (current != null)
        {
            if (count == k)
                return current.data;
            else
            {
                current = current.left;
                count--;
            }
        }

        return -1;


    } // end of function FindkThSmallestElemet
Lerner
quelle
3
Ich glaube nicht, dass diese Lösung funktionieren wird. Was ist, wenn sich der kleinste K-te im rechten Unterbaum des Baumknotens befindet?
Anil Vishnoi
0

Nun, wir können einfach die Durchlaufreihenfolge verwenden und das besuchte Element auf einen Stapel schieben. pop k wie oft, um die Antwort zu bekommen.

Wir können auch nach k Elementen anhalten

kartheek babu
quelle
1
Dies ist keine optimale Lösung
Bragboy
0

Lösung für den vollständigen BST-Fall: -

Node kSmallest(Node root, int k) {
  int i = root.size(); // 2^height - 1, single node is height = 1;
  Node result = root;
  while (i - 1 > k) {
    i = (i-1)/2;  // size of left subtree
    if (k < i) {
      result = result.left;
    } else {
      result = result.right;
      k -= i;
    }  
  }
  return i-1==k ? result: null;
}
gvijay
quelle
0

Der Linux-Kernel verfügt über eine hervorragende erweiterte Rot-Schwarz-Baum-Datenstruktur, die rangbasierte Operationen in O (log n) in linux / lib / rbtree.c unterstützt.

Einen sehr groben Java-Port finden Sie auch unter http://code.google.com/p/refolding/source/browse/trunk/core/src/main/java/it/unibo/refolding/alg/RbTree.java , zusammen mit RbRoot.java und RbNode.java. Das n-te Element kann durch Aufrufen von RbNode.nth (RbNode-Knoten, int n) erhalten werden, wobei die Wurzel des Baums übergeben wird.

Daniel
quelle
0

Hier ist eine kurze Version in C # , die das k-te kleinste Element zurückgibt , jedoch die Übergabe von k als ref-Argument erfordert (es ist der gleiche Ansatz wie bei @prasadvk):

Node FindSmall(Node root, ref int k)
{
    if (root == null || k < 1)
        return null;

    Node node = FindSmall(root.LeftChild, ref k);
    if (node != null)
        return node;

    if (--k == 0)
        return node ?? root;
    return FindSmall(root.RightChild, ref k);
}

Es ist O (log n), um den kleinsten Knoten zu finden , und dann O (k), um zum k-ten Knoten zu gelangen, also ist es O (k + log n).

Erhhung
quelle
Wie wäre es mit der Java-Version?
Henley Chiu
0

Ich konnte keinen besseren Algorithmus finden. Also habe ich beschlossen, einen zu schreiben. Korrigieren Sie mich, wenn dies falsch ist.

class KthLargestBST{
protected static int findKthSmallest(BSTNode root,int k){//user calls this function
    int [] result=findKthSmallest(root,k,0);//I call another function inside
    return result[1];
}
private static int[] findKthSmallest(BSTNode root,int k,int count){//returns result[]2 array containing count in rval[0] and desired element in rval[1] position.
    if(root==null){
        int[]  i=new int[2];
        i[0]=-1;
        i[1]=-1;
        return i;
    }else{
        int rval[]=new int[2];
        int temp[]=new int[2];
        rval=findKthSmallest(root.leftChild,k,count);
        if(rval[0]!=-1){
            count=rval[0];
        }
        count++;
        if(count==k){
            rval[1]=root.data;
        }
        temp=findKthSmallest(root.rightChild,k,(count));
        if(temp[0]!=-1){
            count=temp[0];
        }
        if(temp[1]!=-1){
            rval[1]=temp[1];
        }
        rval[0]=count;
        return rval;
    }
}
public static void main(String args[]){
    BinarySearchTree bst=new BinarySearchTree();
    bst.insert(6);
    bst.insert(8);
    bst.insert(7);
    bst.insert(4);
    bst.insert(3);
    bst.insert(4);
    bst.insert(1);
    bst.insert(12);
    bst.insert(18);
    bst.insert(15);
    bst.insert(16);
    bst.inOrderTraversal();
    System.out.println();
    System.out.println(findKthSmallest(bst.root,11));
}

}}

Laxman
quelle
0

Hier ist der Java-Code,

max (Knotenwurzel, int k) - um den k-ten größten zu finden

min (Node root, int k) - um kth Smallest zu finden

static int count(Node root){
    if(root == null)
        return 0;
    else
        return count(root.left) + count(root.right) +1;
}
static int max(Node root, int k) {
    if(root == null)
        return -1;
    int right= count(root.right);

    if(k == right+1)
        return root.data;
    else if(right < k)
        return max(root.left, k-right-1);
    else return max(root.right, k);
}

static int min(Node root, int k) {
    if (root==null)
        return -1;

    int left= count(root.left);
    if(k == left+1)
        return root.data;
    else if (left < k)
        return min(root.right, k-left-1);
    else
        return min(root.left, k);
}
code_2_peep
quelle
0

das würde auch funktionieren. Rufen Sie einfach die Funktion mit maxNode im Baum auf

def k_largest (self, node, k): wenn k <0: return None
wenn k == 0: return node else: k - = 1 return self.k_largest (self.predecessor (node), k)

user2229805
quelle
0

Ich denke, dies ist besser als die akzeptierte Antwort, da der ursprüngliche Baumknoten nicht geändert werden muss, um die Anzahl seiner untergeordneten Knoten zu speichern.

Wir müssen nur die In-Order-Traversal verwenden, um den kleinsten Knoten von links nach rechts zu zählen. Stoppen Sie die Suche, sobald die Anzahl gleich K ist.

private static int count = 0;
public static void printKthSmallestNode(Node node, int k){
    if(node == null){
        return;
    }

    if( node.getLeftNode() != null ){
        printKthSmallestNode(node.getLeftNode(), k);
    }

    count ++ ;
    if(count <= k )
        System.out.println(node.getValue() + ", count=" + count + ", k=" + k);

    if(count < k  && node.getRightNode() != null)
        printKthSmallestNode(node.getRightNode(), k);
}
Jinshui
quelle
0

Der beste Ansatz ist bereits vorhanden. Aber ich möchte einen einfachen Code dafür hinzufügen

int kthsmallest(treenode *q,int k){
int n = size(q->left) + 1;
if(n==k){
    return q->val;
}
if(n > k){
    return kthsmallest(q->left,k);
}
if(n < k){
    return kthsmallest(q->right,k - n);
}

}}

int size(treenode *q){
if(q==NULL){
    return 0;
}
else{
    return ( size(q->left) + size(q->right) + 1 );
}}
PrashantKumarNirmal
quelle
0

Verwenden der Hilfsergebnisklasse, um zu verfolgen, ob ein Knoten gefunden wurde und aktuell k.

public class KthSmallestElementWithAux {

public int kthsmallest(TreeNode a, int k) {
    TreeNode ans = kthsmallestRec(a, k).node;
    if (ans != null) {
        return ans.val;
    } else {
        return -1;
    }
}

private Result kthsmallestRec(TreeNode a, int k) {
    //Leaf node, do nothing and return
    if (a == null) {
        return new Result(k, null);
    }

    //Search left first
    Result leftSearch = kthsmallestRec(a.left, k);

    //We are done, no need to check right.
    if (leftSearch.node != null) {
        return leftSearch;
    }

    //Consider number of nodes found to the left
    k = leftSearch.k;

    //Check if current root is the solution before going right
    k--;
    if (k == 0) {
        return new Result(k - 1, a);
    }

    //Check right
    Result rightBalanced = kthsmallestRec(a.right, k);

    //Consider all nodes found to the right
    k = rightBalanced.k;

    if (rightBalanced.node != null) {
        return rightBalanced;
    }

    //No node found, recursion will continue at the higher level
    return new Result(k, null);

}

private class Result {
    private final int k;
    private final TreeNode node;

    Result(int max, TreeNode node) {
        this.k = max;
        this.node = node;
    }
}
}
Alex Fedulov
quelle
0

Python-Lösung Zeitkomplexität: O (n) Raumkomplexität: O (1)

Die Idee ist, Morris Inorder Traversal zu verwenden

class Solution(object):
def inorderTraversal(self, current , k ):
    while(current is not None):    #This Means we have reached Right Most Node i.e end of LDR traversal

        if(current.left is not None):  #If Left Exists traverse Left First
            pre = current.left   #Goal is to find the node which will be just before the current node i.e predecessor of current node, let's say current is D in LDR goal is to find L here
            while(pre.right is not None and pre.right != current ): #Find predecesor here
                pre = pre.right
            if(pre.right is None):  #In this case predecessor is found , now link this predecessor to current so that there is a path and current is not lost
                pre.right = current
                current = current.left
            else:                   #This means we have traverse all nodes left to current so in LDR traversal of L is done
                k -= 1
                if(k == 0):
                    return current.val
                pre.right = None       #Remove the link tree restored to original here 
                current = current.right
        else:               #In LDR  LD traversal is done move to R 
            k -= 1
            if(k == 0):
                return current.val
            current = current.right

    return 0

def kthSmallest(self, root, k):
    return self.inorderTraversal( root , k  )
Manish Chauhan
quelle
-1

Ich habe eine nette Funktion geschrieben, um das k-te kleinste Element zu berechnen. Ich verwende die Durchquerung in der richtigen Reihenfolge und halte an, wenn das k-te kleinste Element erreicht ist.

void btree::kthSmallest(node* temp, int& k){
if( temp!= NULL)   {
 kthSmallest(temp->left,k);       
 if(k >0)
 {
     if(k==1)
    {
      cout<<temp->value<<endl;
      return;
    }

    k--;
 }

 kthSmallest(temp->right,k);  }}
Tarunjit Singh
quelle
Es wurden keine Metriken angegeben, warum dies optimal ist. In großen und kleinen Fällen
Woot4Moo
-1
int RecPrintKSmallest(Node_ptr head,int k){
  if(head!=NULL){
    k=RecPrintKSmallest(head->left,k);
    if(k>0){
      printf("%c ",head->Node_key.key);
      k--;
    }
    k=RecPrintKSmallest(head->right,k);
  }
  return k;
}
Ebrahim Saada
quelle
2
Bitte begleiten Sie den Code immer mit einer Beschreibung, was er tut und wie er zur Lösung des Problems beiträgt.
Ren
-1
public TreeNode findKthElement(TreeNode root, int k){
    if((k==numberElement(root.left)+1)){
        return root;
    }
    else if(k>numberElement(root.left)+1){
        findKthElement(root.right,k-numberElement(root.left)-1);
    }
    else{
        findKthElement(root.left, k);
    }
}

public int numberElement(TreeNode node){
    if(node==null){
        return 0;
    }
    else{
        return numberElement(node.left) + numberElement(node.right) + 1;
    }
}
Amazon Ich komme
quelle
-1
public static Node kth(Node n, int k){
    Stack<Node> s=new Stack<Node>();
    int countPopped=0;
    while(!s.isEmpty()||n!=null){
      if(n!=null){
        s.push(n);
        n=n.left;
      }else{
        node=s.pop();
        countPopped++;
        if(countPopped==k){
            return node;
        }
        node=node.right;

      }
  }

}}

Ryan
quelle