hello-algo/ja/docs/chapter_tree/exercises.md

練習問題

知識の確認

完全二分木・全二分木・パーフェクト二分木

次の二つの配列は、二分木をレベル順に表しています。None は空の位置を表します。

• 木 A：[1, 2, 3, 4, 5, 6]
• 木 B：[1, 2, 3, None, None, 6, 7]

1. どちらが完全二分木ですか。
2. どちらが全二分木、つまり葉以外のすべてのノードに二つの子がある木ですか。
3. この二つの中にパーフェクト二分木はありますか。それぞれ理由を説明してください。

??? success "解答例"

1. 木 A は完全二分木です。埋まっていないのは最下層だけで、ノードは左から右へ連続して並んでいます。
    木 B は完全二分木ではありません。最下層の左側に空きがあるのに、右側にはノードがあるためです。

2. 木 B は全二分木です。ノード 1 と 3 はそれぞれ二つの子を持ち、ほかはすべて葉です。
    木 A は全二分木ではありません。ノード 3 にあるのは左の子 6 だけだからです。

3. どちらも最下層が完全には埋まっていないため、パーフェクト二分木ではありません。

同じ木を走査する三つの順序

配列 [1, 2, 3, 4, 5, 6, 7] を、レベル順に完全二分木へ格納します。

1. この木を描いてください。
2. 行きがけ順、通りがけ順、帰りがけ順の走査列を書いてください。
3. 通りがけ順の列で、根ノード 1 の左側と右側の列は、それぞれ木のどの部分に対応しますか。

??? success "解答例"

1. 木は次のようになります。

    ```text
          1
        /   \
       2     3
      / \   / \
     4   5 6   7
    ```

2. 行きがけ順は `1, 2, 4, 5, 3, 6, 7`、
    通りがけ順は `4, 2, 5, 1, 6, 3, 7`、
    帰りがけ順は `4, 5, 2, 6, 7, 3, 1` です。

3. 根ノード 1 の左側の `4, 2, 5` は、左部分木の通りがけ順の列です。
    右側の `6, 3, 7` は、右部分木の通りがけ順の列です。

二つの二分探索木を比べる

次の二つの列を、それぞれ空の二分探索木へ左から右へ順に挿入します。

• 列 A：[4, 2, 6, 1, 3, 5, 7]
• 列 B：[1, 2, 3, 4, 5, 6, 7]

1. 7 を探すときに通るノードを、それぞれ書いてください。
2. 高さを、根から最も遠い葉までに通る辺の数とすると、それぞれの木の高さはいくつですか。
3. 前の二問から、7 を探す効率は二つの木で同じだと思いますか。木の形と探索経路に基づいて理由を説明してください。

??? success "解答例"

1. 列 A で作った木の探索経路は `4 → 6 → 7`、
    列 B で作った木の探索経路は `1 → 2 → 3 → 4 → 5 → 6 → 7` です。

2. 一つ目はすべての層が埋まっており、高さは 2 です。二つ目は右の子しかなく、高さは 6 です。

3. 7 を探す効率は異なります。挿入順によって二分探索木の形と高さが変わるためです。7 を探すとき、一つ目の木で通るのは 3 個のノードだけですが、
    二つ目では 7 個のノードを順に通る必要があります。木が高いほど、最悪の場合に経路に沿って比較するノード数が増えます。

プログラミング演習

二分木の最大の深さ

二分木の根ノード root が与えられます。各ノードは整数値と、左右の子への参照を持ちます。

根から最も遠い葉までに通るノード数を、二分木の最大の深さと呼びます。この木の最大の深さを返してください。空の木の最大の深さは 0 とします。 再帰を使って解いてください。

??? tip "解くためのヒント"

1. この問題ではノード数で深さを数えます。根が一つだけなら、最大の深さは 1 です
2. 再帰関数は、現在のノードを根とする部分木の最大の深さを返すようにします
3. 空のノードでは 0、それ以外では max(depth(left), depth(right)) + 1 を返します

LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }

二分木を層ごとに走査する

二分木の根ノード root が与えられます。キューを使って上から下へ層ごとに全ノードを訪問し、同じ層では左から右の順に訪問してください。

二次元配列を返してください。最初の部分配列には根の層のノード値、二番目には次の層のノード値、というように格納します。 木が空なら、空配列を返してください。

??? tip "解くためのヒント"

1. レベル順走査では、先に入ったノードを先に訪問するため、キューを使います
2. 各反復の開始時にキューにあるノードは、ちょうど同じ層に属しています
3. まずキューの長さを記録し、その個数だけノードを取り出して、それぞれの子を追加します

LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }

二分探索木の k 番目に小さい要素

二分探索木に n 個のノードがあり、各ノードの値はすべて異なります。 全ノードの値を昇順に並べ、その位置に 1 から番号を付けます。

根ノード root と、1 <= k <= n を満たす整数 k が与えられます。k 番目のノードの値を返してください。 先に全ノードの値を集めず、通りがけ順の走査中に直接答えを見つけてください。

??? tip "解くためのヒント"

1. 二分探索木の通りがけ順走査では、ノードの値を小さい順に訪問します
2. 通りがけ順では左部分木、現在のノード、右部分木の順に処理します。現在のノードを訪問したら、個数を 1 増やします
3. 個数が初めて k に達したときのノード値が答えです。それ以降は走査する必要がありません

LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }