完全二分木でノードの深さを求める処理を穴埋めする

解説

完全二分木の配列表現では、要素番号 i のノードの親は要素番号 i ÷ 2（切り捨て）にある。根の要素番号は 1 なので、pos が 1 より大きい間だけ親をたどればよい。 【トレース例】getDepth(5) を呼んだ場合（ノード 5 は根→左の子→右の子の位置、深さ 2）: 初期状態: pos = 5, depth = 0 1回目: 5 > 1 → true, pos ← 5 ÷ 2 = 2, depth ← 1 2回目: 2 > 1 → true, pos ← 2 ÷ 2 = 1, depth ← 2 3回目: 1 > 1 → false → ループ終了 return 2 深さ 2 が正しく返される。 誤答の確認: ・ア／ウ（pos > 0 または pos ≧ 1）: pos = 1 のときもう1回ループが回り depth が 3 になる。 ・エ（pos - 1）: 親に移動せず番号を 1 ずつ減らすだけなので depth = 4 になる。 ・オ（pos > 0 かつ pos - 1）: depth = 5 になる。

選択肢ごとの解説

ア

条件が pos > 0 だと、pos が 1（根）のとき pos ÷ 2 = 0 となってもループをもう1回実行し、深さを 1 多く数えてしまう。

イ

正解。pos が根（1）より大きい間だけ親をたどり、たどった回数が深さになる。

ウ

pos ≧ 1 は pos > 0 と同義（pos は正整数）であり、アと同じく深さを 1 多く数える誤りになる。

エ

pos - 1 は完全二分木の親ではなく単に番号を 1 ずつ減らすだけなので、深さではなく pos - 1 が返る。

オ

条件・更新式とも誤り。pos を 1 ずつ減らし 0 になるまで繰り返すため、pos そのものが返される。

登録すると解いた結果が残り、間違えた問題は日をおいて復習に出ます。