Найти kth наименьшее в bst с помощью рекурсивного порядка

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

Любая идея??

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. Когда мы ищем слева, проблема в том, чтобы найти kth наименьшее. Однако при поиске справа нам нужно найти 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];
}