binary-search-tree - 在二叉搜索树中找到第 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. 如果允许您使用额外的内存，请将元素复制到动态分配的排序数组（使用中序遍历）并返回第 k 个元素。