概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
問題
102. Binary Tree Level Order Traversal
二分木のルートが与えられたとき、深さ毎の値をリストにして返せ。
（階層ごとにリストを作成）
制約
- ツリーのノード数は
[0, 5000]の範囲 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
解説
与えられたrootノードから階層ごとに値をまとめたリストを作成し、階層ごとのリストをさらにリスト化したものを返す問題です。
BFSを使用した問題ですので、BFSに慣れていない方はまずはこちらの問題から解くことをお勧めします。
C#で解くLeetCode「111. Minimum Depth of Binary Tree」 はじめに、nullを渡されたら空のリストを返す例外処理を書きます。
次に深さ毎の値のリストをリストで管理するための全体の値管理リストとBFSを行うための探索対象キューを作成してrootを追加します。
public class Solution {
public IList<IList<int>> LevelOrder(TreeNode root)
{
// nullが渡されたら空のリストを返す
if (root is null)
{
return new List<IList<int>>();
}
// 深さ毎に値のリストを管理するための全体の値管理リストを作成
var depthList = new List<IList<int>>();
// 探索対象のノードを管理するためのキューを作成してrootを追加
var nodeQueue = new Queue<TreeNode>();
nodeQueue.Enqueue(root);
}
}準備ができたらさっそくBFSを始めます。
まずは探索対象が無くなるまで繰り返すwhile文を用意します。このwhileで繰り返されるループは階層が変わるごとに繰り返されるループと思ってください。
そして現在の探索対象の数を確認して一時保存します。ここで保存される値は現在の階層にあるノードの数です。
さらに階層ごとに値をリスト化する必要があるので、ここでリストも作成しておきます。
public class Solution {
public IList<IList<int>> LevelOrder(TreeNode root)
{
// nullが渡されたら空のリストを返す
if (root is null)
{
return new List<IList<int>>();
}
// 深さ毎に値のリストを管理するための全体の値管理リストを作成
var depthList = new List<IList<int>>();
// 探索対象のノードを管理するためのキューを作成してrootを追加
var nodeQueue = new Queue<TreeNode>();
nodeQueue.Enqueue(root);
// 探索対象が無くなるまで繰り返す
while (nodeQueue.Count != 0)
{
// 現在の探索対象の数を確認して一時保存
var levelsCount = nodeQueue.Count;
// 現在探索している深さの値を管理するための値管理リストを作成
var nodeValues = new List<int>();
}
}
}次に確認処理に入ります。
現在の階層のノードを一つずつ確認するので先ほど一時保存した数だけループするfor文を作成します。
注意点としてはここで直接nodeQueue.Countを使用しないでください。
そしてノードをキューから取り出して値を事前に作成した値管理リストに追加します。
さらに左右のノードを確認して存在していれば次の階層の探索対象としてキューに左右のノードを追加します。
ループが終わったら値管理リストを全体のリストに追加して次の階層の探索に移ります。
public class Solution {
public IList<IList<int>> LevelOrder(TreeNode root)
{
// nullが渡されたら空のリストを返す
if (root is null)
{
return new List<IList<int>>();
}
// 深さ毎に値のリストを管理するための全体の値管理リストを作成
var depthList = new List<IList<int>>();
// 探索対象のノードを管理するためのキューを作成してrootを追加
var nodeQueue = new Queue<TreeNode>();
nodeQueue.Enqueue(root);
// 探索対象が無くなるまで繰り返す
while (nodeQueue.Count != 0)
{
// 現在の探索対象の数を確認して一時保存
var levelsCount = nodeQueue.Count;
// 現在探索している深さの値を管理するための値管理リストを作成
var nodeValues = new List<int>();
// 現在探索している深さのノードの数だけ繰り返す
for (int i = 0; i < levelsCount; i++)
{
// 探索対象からノードを一つ取り出して値を値管理リストに保存
var node = nodeQueue.Dequeue();
nodeValues.Add(node.val);
// 対象のノードの左にノードがあれば探索対象リストに追加
if (node.left is not null)
{
nodeQueue.Enqueue(node.left);
}
// 対象のノードの右にノードがあれば探索対象リストに追加
if (node.right is not null)
{
nodeQueue.Enqueue(node.right);
}
}
// 現在の深さの値管理リストを全体の値管理リストに追加
depthList.Add(nodeValues);
}
// 全体の値管理リストを返す
return depthList;
}
}
探索対象がなくなったらすべてのノードを確認したことになるので、最後に全体のリストを返して終了です。
ソースコード
public class Solution {
public IList<IList<int>> LevelOrder(TreeNode root)
{
// nullが渡されたら空のリストを返す
if (root is null)
{
return new List<IList<int>>();
}
// 深さ毎に値のリストを管理するための全体の値管理リストを作成
var depthList = new List<IList<int>>();
// 探索対象のノードを管理するためのキューを作成してrootを追加
var nodeQueue = new Queue<TreeNode>();
nodeQueue.Enqueue(root);
// 探索対象が無くなるまで繰り返す
while (nodeQueue.Count != 0)
{
// 現在の探索対象の数を確認して一時保存
var levelsCount = nodeQueue.Count;
// 現在探索している深さの値を管理するための値管理リストを作成
var nodeValues = new List<int>();
// 現在探索している深さのノードの数だけ繰り返す
for (int i = 0; i < levelsCount; i++)
{
// 探索対象からノードを一つ取り出して値を値管理リストに保存
var node = nodeQueue.Dequeue();
nodeValues.Add(node.val);
// 対象のノードの左にノードがあれば探索対象リストに追加
if (node.left is not null)
{
nodeQueue.Enqueue(node.left);
}
// 対象のノードの右にノードがあれば探索対象リストに追加
if (node.right is not null)
{
nodeQueue.Enqueue(node.right);
}
}
// 現在の深さの値管理リストを全体の値管理リストに追加
depthList.Add(nodeValues);
}
// 全体の値管理リストを返す
return depthList;
}
}