1週間前のテストで次の問題がありました。成績は戻っていませんが、私の解決策は問題のすべての基本ケースを完全に対象としていたわけではありません。
声明は次のとおりです。
Binary Searcht ツリーの場合、与えられた整数 k 以上のキーを持つノードの数を計算するアルゴリズムを (疑似コードを使用して) 書きます。アルゴリズムは、最悪の場合の時間 O(h) で実行する必要があります。ここで、h は二分探索木の高さです。
時間 O(1) で実行され、n をルートとするサブツリーのノード数 (n 自体を含む) を返すメソッド subtreeSize(treeNode n) が与えられたとします。
これが私の解決策です：
nbNodesGreaterEqual(treeNode n, int k){
if(n == null) return 0;
if(n.getValue() >= k) return 1 + substreeSize(n.getRightChild()) + nbNodesGreaterEqual(n.getLeftChild(), k);
if(n.getValue < k) return nbNodesGreaterEqual(n.getRightChild,k);
}
アルゴリズムは完成していますか? また、すべてのノードを通過しない通常のバイナリ ツリー (BST ではない) に対して同じアルゴリズムを記述する方法はありますか?