Znajdź k-ty najmniejszy element w drzewie wyszukiwania binarnego w Optymalny sposób


112

Muszę znaleźć k-ty najmniejszy element w drzewie wyszukiwania binarnego bez użycia zmiennej statycznej / globalnej. Jak to skutecznie osiągnąć? Rozwiązaniem, które mam na myśli, jest wykonanie operacji w O (n), najgorszym przypadku, ponieważ planuję wykonać wewnętrzne przejście całego drzewa. Ale w głębi duszy czuję, że nie używam tutaj właściwości BST. Czy moje założenie jest poprawne, czy jest dostępne lepsze?


7
Czy drzewo jest zrównoważone?
kennytm

To nie jest. Ale czy jest optymalny sposób, gdyby był zrównoważony?
bragboy,

1
Jeśli przeszukasz „Statystyki zamówień”, znajdziesz to, czego potrzebujesz.
RAL

Wydaje mi się, że większość poniższych odpowiedzi, podczas gdy poprawne są oszustwami, ponieważ używają pewnego rodzaju zmiennej globalnej (niezależnie od tego, czy jest to odniesienie do liczby całkowitej, czy zmienna, która jest zmniejszana i zwracana). Jeśli absolutnie żadne z nich nie jest dozwolone, użyłbym rekurencji bez przekazywania żadnych odniesień.
Henley Chiu

Odpowiedzi:


170

Oto tylko zarys pomysłu:

W BST lewe poddrzewo węzła Tzawiera tylko elementy mniejsze niż wartość przechowywana w T. Jeśli kjest mniejsza niż liczba elementów w lewym poddrzewie, to knajmniejszy element musi należeć do lewego poddrzewa. W przeciwnym razie, jeśli kjest większy, to knajmniejszy element znajduje się w prawym poddrzewie.

Możemy rozszerzyć BST, aby każdy węzeł w nim przechował liczbę elementów w swoim lewym poddrzewie (załóżmy, że lewe poddrzewo danego węzła zawiera ten węzeł). Dzięki tej informacji łatwo jest przejść przez drzewo, wielokrotnie prosząc o liczbę elementów w lewym poddrzewie, aby zdecydować, czy powtórzyć w lewym, czy prawym poddrzewie.

Teraz załóżmy, że jesteśmy w węźle T:

  1. Jeśli k == liczba_elementów (lewe poddrzewo T) , wówczas szukaną odpowiedzią jest wartość w węźle T.
  2. Jeśli k> liczba_elementów (lewe poddrzewo T) , to oczywiście możemy zignorować lewe poddrzewo, ponieważ te elementy będą również mniejsze niż to knajmniejsze. Tak więc sprowadzamy problem do znalezienia k - num_elements(left subtree of T)najmniejszego elementu odpowiedniego poddrzewa.
  3. Jeśli k <liczba_elementów (lewe poddrzewo T) , to knajmniejsze znajduje się gdzieś w lewym poddrzewie, więc sprowadzamy problem do znalezienia ktego najmniejszego elementu w lewym poddrzewie.

Analiza złożoności:

To wymaga O(depth of node)czasu, co O(log n)w najgorszym przypadku ma miejsce na zrównoważonym BST lub O(log n)średnio w przypadku losowego BST.

BST wymaga O(n)pamięci, a inny O(n)do przechowywania informacji o liczbie elementów. Wszystkie operacje BST wymagają O(depth of node)czasu, a O(depth of node)utrzymanie informacji o liczbie elementów do wstawienia, usunięcia lub obrotu węzłów zajmuje więcej czasu. Dlatego przechowywanie informacji o liczbie elementów w lewym poddrzewie zachowuje złożoność przestrzenną i czasową BST.


59
Aby znaleźć N-ty najmniejszy element, wystarczy zapisać rozmiar lewego poddrzewa. Użyłbyś rozmiaru prawego poddrzewa, jeśli chciałbyś również znaleźć N-ty największy element. W rzeczywistości możesz to jednak obniżyć: zapisz całkowity rozmiar drzewa w katalogu głównym, a rozmiar lewego poddrzewa. Kiedy potrzebujesz zmienić rozmiar prawego poddrzewa, możesz odjąć rozmiar lewego drzewa od całkowitego rozmiaru.
Jerry Coffin

37
Taki rozszerzony BST nazywany jest „drzewem statystyk zamówień”.
Daniel

10
@Ivlad: w kroku 2: Myślę, że "k - num_elements" powinno być "k - num_elements -1", ponieważ musisz również dołączyć element główny.
rozumiem

1
@understack - nie, jeśli założysz, że katalog główny jest częścią poddrzewa.
IVlad

16
Jeśli drzewo nie zawiera pola zawierającego „liczbę elementów w jego lewym i prawym poddrzewie”, metoda zakończy się na BigO (n), ponieważ będziesz musiał przejść prawe lub lewe poddrzewo w każdym węźle, aby obliczyć indeks k bieżącego węzła.
Robert S. Barnes

68

Prostszym rozwiązaniem byłoby wykonanie przejścia w kolejności i śledzenie aktualnie drukowanego elementu (bez jego drukowania). Kiedy osiągniemy k, wypisz element i pomiń resztę przechodzenia po drzewie.

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); 
}

1
+1: Pomysł jest w dobrym kierunku, ale niektóre luźne końce mogą wymagać dokręcenia; patrz stackoverflow.com/a/23069077/278326
Arun,

1
Podoba mi się to rozwiązanie, ponieważ BST jest już zamówiony, wystarczy przejść.
Merlin,

3
Jeśli n jest zbliżone do całkowitej liczby węzłów w tym drzewie, działanie algorytmu zajmie O (n) czasu, aby zakończyć, co jest złe dla wybranej odpowiedzi-O (log n)
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;
    }

to jest moja implementacja w C # w oparciu o powyższy algorytm, po prostu pomyślałem, że opublikuję go, aby ludzie mogli lepiej zrozumieć, że działa dla mnie

dziękuję IVlad


11

Prostszym rozwiązaniem byłoby wykonanie przejścia w kolejności i śledzenie aktualnie drukowanego elementu za pomocą licznika k. Kiedy osiągniemy k, wydrukuj element. Środowisko wykonawcze to O (n). Pamiętaj, że zwracany typ funkcji nie może być void, musi zwracać zaktualizowaną wartość k po każdym wywołaniu rekurencyjnym. Lepszym rozwiązaniem byłby rozszerzony BST z posortowaną wartością pozycji w każdym węźle.

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;
}

Wydaje mi się, że twoje rozwiązanie jest lepsze pod względem złożoności przestrzeni w porównaniu z rozszerzonym BST.
zach.

Wyszukiwanie nie kończy się nawet po znalezieniu k-tego najmniejszego elementu.
Vineeth Chitteti

10

// dodaj wersję java bez rekursji

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();
        }
    }
}

Podoba mi się to rozwiązanie i odpowiadające mu rekurencyjne. Szczerze mówiąc, większość odpowiedzi na to pytanie jest zbyt zagmatwana / skomplikowana, aby je przeczytać.
Henley Chiu

Uwielbiam to rozwiązanie! Jasne i świetne!
Rugal

To rozwiązanie polega na przechodzeniu przez drzewo w kolejności i zmniejszaniu licznika po odwiedzeniu węzła, aby później zatrzymać się, gdy licznik osiągnie zero. Najgorszy przypadek jest wtedy rzędu O (n). Nie jest to najbardziej optymalne w porównaniu z rozwiązaniami rekurencyjnymi @ IVlad, których najgorszy przypadek ma O (log n)
Jorge P.


4

Biorąc pod uwagę tylko zwykłe drzewo wyszukiwania binarnego, prawie wszystko, co możesz zrobić, to zacząć od najmniejszego i przejść w górę, aby znaleźć właściwy węzeł.

Jeśli masz zamiar robić to bardzo często, możesz dodać atrybut do każdego węzła oznaczający, ile węzłów znajduje się w jego lewym poddrzewie. Używając tego, możesz zejść z drzewa bezpośrednio do właściwego węzła.


4

Rekurencyjny spacer w kolejności z licznikiem

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

Pomysł jest podobny do rozwiązania @prasadvk, ale ma pewne wady (patrz uwagi poniżej), więc zamieszczam to jako osobną odpowiedź.

// 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 );
}

Uwagi (i różnice w stosunku do rozwiązania @ prasadvk):

  1. if( counter == k )test jest wymagany w trzech miejscach: (a) za lewym poddrzewem, (b) za korzeniem i (c) po prawym poddrzewie. Ma to na celu zapewnienie, że k-ty element zostanie wykryty we wszystkich lokalizacjach , tj. Niezależnie od poddrzewa, w którym się znajduje.

  2. if( result == -1 )wymagany jest test, aby upewnić się, że drukowany jest tylko element wynikowy , w przeciwnym razie drukowane są wszystkie elementy, począwszy od k-tego najmniejszego do korzenia.


Złożoność czasowa tego rozwiązania jest to O(k + d), gdzie djest maksymalna głębokość drzewa. Dlatego używa zmiennej globalnej, counterale jest to nielegalne w przypadku tego pytania.
Valentin Shergin,

Cześć Arun, czy możesz wyjaśnić na przykładzie. Nie rozumiem tego szczególnie twojego pierwszego punktu.
Andy897,

3

Za nie wynosi przeszukiwania drzewa, zajmuje O (n) .

W przypadku zrównoważonego drzewa wyszukiwania, w najgorszym przypadku wymaga O (k + log n), ale tylko O (k) w amortyzacji sensie.

Posiadanie dodatkowej liczby całkowitej dla każdego węzła i zarządzanie nią: rozmiar poddrzewa daje O (log n) złożoność czasową . Takie zrównoważone drzewo wyszukiwania jest zwykle nazywane RankTree.

Ogólnie rzecz biorąc, istnieją rozwiązania (nie oparte na drzewie).

Pozdrowienia.


1

Działa to dobrze: status: to tablica przechowująca informację o znalezieniu elementu. k: to k-ty element do znalezienia. count: śledzi liczbę węzłów pokonanych podczas przechodzenia przez drzewo.

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;
}

1

Chociaż zdecydowanie nie jest to optymalne rozwiązanie problemu, jest to kolejne potencjalne rozwiązanie, które moim zdaniem może być interesujące dla niektórych osób:

/**
 * 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 );
}

1

podpis:

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

zadzwoń jako:

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

definicja:

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;
}

1

Cóż, oto moje 2 centy ...

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;
 }

0

To jest to, co myślałem i działa. Będzie działać za (log n)

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

3
nie sądzę, żeby to rozwiązanie zadziałało. A co, jeśli najmniejsze K-ty znajduje się w prawym poddrzewie węzła drzewa?
Anil Vishnoi,

0

Cóż, możemy po prostu użyć przemierzania kolejności i włożyć odwiedzony element na stos. pop k kilka razy, aby uzyskać odpowiedź.

możemy też zatrzymać się po k elementów


1
to nie jest optymalne rozwiązanie
chwalić się,

0

Rozwiązanie dla całego przypadku BST: -

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;
}

0

Jądro Linuksa ma doskonałą, powiększoną czerwono-czarną strukturę danych drzewa, która obsługuje operacje oparte na rangach w O (log n) w linux / lib / rbtree.c.

Bardzo prymitywny port Java można również znaleźć pod adresem http://code.google.com/p/refolding/source/browse/trunk/core/src/main/java/it/unibo/refolding/alg/RbTree.java , razem z RbRoot.java i RbNode.java. N-ty element można uzyskać, wywołując RbNode.nth (węzeł RbNode, int n), przekazując do korzenia drzewa.


0

Oto zwięzła wersja w C #, która zwraca k-ty najmniejszy element, ale wymaga przekazania k jako argumentu ref (jest to to samo podejście, co @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);
}

To O (log n), aby znaleźć się najmniejszą węzeł, a następnie O (K) do przejścia do k-tego węzła, tak, że to O (K + log n).


a co z wersją java?
Henley Chiu


0

Nie mogłem znaleźć lepszego algorytmu… więc zdecydowałem się go napisać :) Popraw mnie, jeśli jest źle.

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));
}

}


0

Oto kod java,

max (Node root, int k) - aby znaleźć k-t największy

min (Node root, int k) - aby znaleźć k-t najmniejszy

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);
}

0

to też by działało. po prostu wywołaj funkcję z maxNode w drzewie

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


0

Myślę, że jest to lepsze niż zaakceptowana odpowiedź, ponieważ nie trzeba modyfikować oryginalnego węzła drzewa, aby przechowywać liczbę jego węzłów podrzędnych.

Musimy tylko użyć przechodzenia w kolejności, aby policzyć najmniejszy węzeł od lewej do prawej, przestań szukać, gdy liczba będzie równa K.

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);
}

0

Najlepsze podejście już jest, ale chciałbym dodać do tego prosty kod

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 );
}}

0

Używanie pomocniczej klasy Result do śledzenia znalezienia węzła i bieżącego 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;
    }
}
}

0

Złożoność czasowa rozwiązania Pythona: O (n) Złożoność przestrzeni: O (1)

Pomysł polega na użyciu Morris Inorder Traversal

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  )

-1

Napisałem zgrabną funkcję do obliczania k-tego najmniejszego elementu. Używam przechodzenia w kolejności i zatrzymuję się, gdy osiągnie k-ty najmniejszy element.

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);  }}

Nie podano wskaźników wyjaśniających, dlaczego jest to optymalne. Zarówno w dużych, jak i małych przypadkach
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;
}

2
Zawsze dołączaj do kodu pewien poziom opisu tego, co robi i jak pomaga rozwiązać problem.
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;
    }
}

-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;

      }
  }

}

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.