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