概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
問題
103. Binary Tree Zigzag Level Order Traversal
二分木のルートが与えられたとき階層ごとのノードの値をジグザグにしたリストを返す。
（階層ごとに順番・反転・順番・反転のリストが交互になる）
制約
- ツリーのノード数は
[0, 2000]の範囲 -100 <= Node.val <= 100
解説
与えられたrootノードから階層ごとに値をまとめたリストを作成し、階層ごとのリストをジグザグにリスト化したものを返す問題です。
ジグザグにしていない問題もありますので、まずはそちらから回答してみてください。
C#で解くLeetCode「102. Binary Tree Level Order Traversal」
どちらも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);
// 反転するためのフラグ
var isReversed = false;
}
}準備ができたらさっそくBFSを始めます。
まずは探索対象が無くなるまで繰り返すwhile文を用意します。このwhileで繰り返されるループは階層が変わるごとに繰り返されるループと思ってください。
そして現在の探索対象の数を確認して一時保存します。ここで保存される値は現在の階層にあるノードの数です。
さらに階層ごとに値をリスト化する必要があるので、ここでリストも作成しておきます。
ジグザグを表すのに反転して追加させる場合もあるため、作成するリストは通常のListクラスではなくLinkedListクラスを使用してください。
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);
// 反転するためのフラグ
var isReversed = false;
// 探索対象が無くなるまで繰り返す
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);
// 反転するためのフラグ
var isReversed = false;
// 探索対象が無くなるまで繰り返す
while (nodeQueue.Count != 0)
{
// 現在の探索対象の数を確認して一時保存
var levelsCount = nodeQueue.Count;
// 現在探索している深さの値を管理するための値管理リストを作成
var nodeValues = new List<int>();
// 現在探索している深さのノードの数だけ繰り返す
for (int i = 0; i < levelsCount; i++)
{
// 探索対象からノードを一つ取り出して値を値管理リストに保存
var node = nodeQueue.Dequeue();
// 反転するか判断し追加する方向を決める
if (!isReversed)
{
nodeValues.AddLast(node.val);
}
else
{
nodeValues.AddFirst(node.val);
}
}
}
}
}さらに左右のノードを確認して存在していれば次の階層の探索対象としてキューに左右のノードを追加します。
ループが終わったら値管理リストを全体のリストに追加して保存する値の方向を反転させ次の階層の探索に移ります。
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);
// 反転するためのフラグ
var isReversed = false;
// 探索対象が無くなるまで繰り返す
while (nodeQueue.Count != 0)
{
// 現在の探索対象の数を確認して一時保存
var levelsCount = nodeQueue.Count;
// 現在探索している深さの値を管理するための値管理リストを作成
var nodeValues = new List<int>();
// 現在探索している深さのノードの数だけ繰り返す
for (int i = 0; i < levelsCount; i++)
{
// 探索対象からノードを一つ取り出して値を値管理リストに保存
var node = nodeQueue.Dequeue();
// 反転するか判断し追加する方向を決める
if (!isReversed)
{
nodeValues.AddLast(node.val);
}
else
{
nodeValues.AddFirst(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);
// 進行方向を反転させる
isReversed = !isReversed;
}
// 全体の値管理リストを返す
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);
// 反転するためのフラグ
var isReversed = false;
// 探索対象が無くなるまで繰り返す
while (nodeQueue.Count > 0)
{
// 現在の探索対象の数を確認して一時保存
var levelsCount = nodeQueue.Count;
// 現在探索している深さの値を管理するための値管理リストを作成
var nodeValues = new LinkedList<int>();
for (int i = 0; i < levelsCount; i++)
{
// 探索対象からノードを一つ取り出して値を値管理リストに保存
var node = nodeQueue.Dequeue();
if (!isReversed)
{
nodeValues.AddLast(node.val);
}
else
{
nodeValues.AddFirst(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.ToList());
// 進行方向を反転させる
isReversed = !isReversed;
}
// 全体の値管理リストを返す
return depthList;ode.right is not null)
{
nodeQueue.Enqueue(node.right);
}
}
// 現在の深さの値管理リストを全体の値管理リストに追加
depthList.Add(nodeValues);
}
// 全体の値管理リストを返す
return depthList;
}
}