概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
問題
111. Minimum Depth of Binary Tree
二分木が与えられたとき、その最小の深さを求めよ。
最小の深さとは、ルートノードから最も近いリーフノードまでの最短経路に沿ったノードの数である。
注：リーフノードとは、子を持たないノードのことである。
制約
- ツリーのノード数は、
[0, 104]の範囲である。 -100 <= Node.val <= 100
解説
二分木の探索を使用した最小の深さを求めます。
似たような問題で最大の深さを求める問題もありますので、以下の記事を参考に合わせて問題を解くことをお勧めします。
C#で解くLeetCode「104. Maximum Depth of Binary Tree」 最大の深さを求める際はDFSを使用しますが、この問題はBFSを使用して解いていきます。
なぜならば、DFSは深さを優先して探索していくため、リーフノードが見つかっていても一番浅いかどうかわかりません。
ですので、すべてのノードを探索する必要があり時間がかかってしまいます。
ですが、BFSだと幅を優先して探索していくので、一番最初に見つかったリーフノードが一番浅いリーフノードということになります。
よって余分な深いノードを探索する必要がなくなり、処理時間の差が生まれます。
それではBFSを使用した深さを求めていきます。
まず初めにrootがnullだった場合の処理を忘れずに記載していきます。
private int MinDepth(TreeNode root)
{
if (root == null)
{
return 0;
}
}次に見つけたノードを要確認対象とするためにキューを用意いたします。
この際、見つけた順（左から順番）にリーフノードかどうか確認していくためリストではなくキューとしてください。rootを探索対象と渡されているので1段目の確認対象として追加しておきます。
そして、確認した深さを記録するための変数を用意いたします。
ここではまだrootはリーフノードかどうか確認していないため、深さの初期値は0とします。
private int MinDepth(TreeNode root)
{
if (root == null)
{
return 0;
}
var queue = new Queue<TreeNode>();
queue.Enqueue(root);
int depth = 0;
}BFS探索は深さ毎に繰り返し確認をするためWhile文で囲み、深さを記録するためdepth変数をインクリメントします。
また、リーフノードではなければ探索対象としてキューに追加してしまうため、確認する前に現在の深さの確認対象数を数えます。
private int MinDepth(TreeNode root)
{
if (root == null)
{
return 0;
}
var queue = new Queue<TreeNode>();
queue.Enqueue(root);
int depth = 0;
// 深さ毎に各ノードを確認
while(queue.Count != 0)
{
// 深さを記録
depth++;
// 現在の深さの確認対象数
var currentTargetCount = queue.Count;
// 確認対象がリーフノードかどうか確認
}
}
次にfor文で現在の深さの探索対象を一つずつリーフノードかどうか確認していきます。
対象をキューから取り出し左右にノードがあるかを確認、ノードが両方ともなければリーフノードなので、現在の深さを返します。
リーフノードでなければ左右それぞれの存在を確認し、存在していれば次の確認対象としてノードをキューに追加します。
for文で囲んでいるので、現在の深さのノードを全て確認したら次の深さへ進み再度確認処理を始めます。
以上で確認処理が終了ですが、while文の外にもreturn を用意しないとコンパイルエラーとなるのでreturnを用意します。
ですが、ここにたどり着きはしないので値は何でもいいですが、たどり着いてしまった場合想定外と分かりやすくするためreturn -1として終了です。
private int MinDepth(TreeNode root)
{
if (root == null)
{
return 0;
}
var queue = new Queue<TreeNode>();
queue.Enqueue(root);
int depth = 0;
// 深さ毎に各ノードを確認
while(queue.Count != 0)
{
// 深さを記録
depth++;
// 現在の深さの探索対象数
var currentTargetCount = queue.Count;
// 確認対象がリーフノードかどうか確認
for (int i = 0; i < currentTargetCount; i++)
{
var target = queue.Dequeue();
// 対象がリーフノードであれば今の深さを返す
if (target.left is null && target.right is null)
{
return depth;
}
// 左のノードが存在していれば左のノードを探索対象に追加
if (target.left != null)
{
queue.Enqueue(target.left);
}
// 右のノードが存在していれば右のノードを探索対象に追加
if (target.right != null)
{
queue.Enqueue(target.right);
}
}
}
// ここにたどり着いたら異常
return -1;
}ソースコード
public class Solution {
private int MinDepth(TreeNode root)
{
if (root == null)
{
return 0;
}
var queue = new Queue<TreeNode>();
queue.Enqueue(root);
int depth = 0;
// 深さ毎に各ノードを確認
while (queue.Count != 0)
{
// 現在探索している深さを記録
depth++;
// 現在の深さの確認対象数
var currentTargetCount = queue.Count;
// 確認対象がリーフノードかどうか確認
for (int i = 0; i < currentTargetCount; i++)
{
var target = queue.Dequeue();
// 対象がリーフノードであれば今の深さを返す
if (target.left is null && target.right is null)
{
return depth;
}
// 左のノードが存在していれば左のノードを探索対象に追加
if (target.left != null)
{
queue.Enqueue(target.left);
}
// 右のノードが存在していれば右のノードを探索対象に追加
if (target.right != null)
{
queue.Enqueue(target.right);
}
}
}
return depth;
}
}