在二叉搜索樹中找到第K個元素

Question

我正在學習二叉搜索樹。我想返回二叉查找樹的有序遍歷的第k個元素。我怎樣才能保持變量'計數'更新或有一些方法可以打破循環，一旦我找到第k個元素並將其打印出來？

public void kthElement(int n, int count, BinaryNode<AnyType> root){ 

    if(root.left !=null) 
     this.kthElement(n, count, root.left); 

    count++; 
    if(count==n){ 
     System.out.println(root.element); 
     } 

    else if(count!=n){ 
     return;} 

    if(root.right != null) 
     this.kthElement(n, count, root.right); 
    } 

Answer 1

我能想到兩個解決方案。

1. 爲每個節點聲明一個字段，說明右子樹和左子樹中有多少元素，從這裏開始應該很容易。
2. 如果您允許使用額外內存，請將元素複製到動態分配的排序數組（使用inorder遍歷）並返回第k個元素。