algorithm - 使用递归顺序在 bst 中找到第 k 个最小的

Question

我试图在 BST 中找到第 k 个最小的。

public void findKthSmallest(BSTNode<T> node, int k) {
    if(node == null) 
        return;
    findKthSmallest(node.left, k);

    count++;
    if (k == count) {
        System.out.println("Kth smallest: " + node.data);
        return;
    }
    findKthSmallest(node.right, k);
}

这里 count 是一个实例变量。我无法弄清楚如何在函数中使用 count 作为参数（局部变量）来实现它，因为它会在函数返回时重置。

任何想法？？

Answer 1

由于这是 Java 并且您没有通过引用传递，因此我认为最简单的方法是修改findKthSmallest以返回以node. 像这样的东西：

public int findKthSmallest(BSTNode<T> node, int k) {
    if(node == null) 
        return 0;
    int left = findKthSmallest(node.left, k);

    if (k == left + 1) {
        System.out.println("Kth smallest: " + node.data);
        return 1;
    }

    return 1 + left + findKthSmallest(node.right, k);
}

Answer 2

我想对 IVlad 的方法做一个小的修正。当我们向左搜索时，问题是找到第 k 个最小的。但是，当向右搜索时，我们需要找到 k-left-1（丢弃左子树+当前节点）。在java中，除了创建一个类之外，我们不能返回多个值。所以通过传递一个数组作为参数来解决这个问题。这是代码：

public int kthSmallest(TreeNode node, int k, TreeNode kthNode[]) {
    int leftCount = 0;
    int rightCount = 0;
    if(node.left!=null) {
        leftCount = kthSmallest(node.left, k, kthNode);
    }
    if(leftCount==k-1) {
        kthNode[0] = node; // We can also return from here
    }
    if(node.right!=null) {
        rightCount = kthSmallest(node.right, k-leftCount-1, kthNode);
    }
    return leftCount + 1 + rightCount;
}

public TreeNode kthSmallest(TreeNode node, int k) {
    TreeNode kNode[] = new TreeNode[1];
    int nodeCount = kthSmallest(node, k, kNode);
    return kNode[0];
}