найти kth самый маленький в bst используя рекурсивный inorder

Question

Я пытаюсь найти kth самый маленький в BST.

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 как параметр (локальный varaible) в функции, так как он получает сбрасывается, когда функция возвращается.

Любая идея ??

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