0

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 を使用して実装する方法を理解できません。

何か案が？？

4

2 に答える 2

3

findKthSmallestこれは Java であり、参照渡しがないため、をルートとするサブツリー内のノード数を返すように変更するのが最も簡単だと思います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);
}
于 2012-06-17T10:29:44.713 に答える
1

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];
}
于 2016-06-15T22:19:40.437 に答える