在bst中使用递归找到kth最小inorder

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作为参数（局部变量）来实现它，因为函数返回时它会重置。

任何想法??

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