在二叉搜索树中找到第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个元素。