mirror of
https://github.com/krahets/hello-algo.git
synced 2026-11-01 21:24:27 +08:00
7257641e0e
* Retranslate the complete Japanese online edition from Chinese * Fit Japanese homepage labels and localize heading permalinks * Point Japanese contribution instructions to the Japanese preview * Replace locale conditionals with multilingual UI tables
127 lines
6.5 KiB
Markdown
127 lines
6.5 KiB
Markdown
# 練習問題
|
||
|
||
## 知識の確認
|
||
|
||
### 完全二分木・全二分木・パーフェクト二分木
|
||
|
||
次の二つの配列は、二分木をレベル順に表しています。`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" }
|