# 練習問題

## 知識の確認

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

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

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

<!-- numbered-subquestions -->

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

??? success "解答例"

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

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

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

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

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

<!-- numbered-subquestions -->

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]`

<!-- numbered-subquestions -->

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](https://leetcode.com/problems/maximum-depth-of-binary-tree/){ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }

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

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

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

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

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

[LeetCode](https://leetcode.com/problems/binary-tree-level-order-traversal/){ .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](https://leetcode.com/problems/kth-smallest-element-in-a-bst/){ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }