概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
問題
108. Convert Sorted Array to Binary Search Tree
要素が昇順にソートされた整数配列numsが与えられたとき、
それを高さバランスのとれた二分探索木に変換せよ。
高さバランスのとれた2分木とは、
各ノードの2つの部分木の深さが1以上違わない2分木のことである。
制約
- 二つの二分木のノード数は
[0, 2000]の範囲である。 -104 <= Node.val <= 104
解説
ソートされた配列から左から順にソートされているバランスのいい二分木を作成する問題です。
DFSを使用した問題ですので、DFSに慣れていない方はまずはこちらの問題から解くことをお勧めします。
C#で解くLeetCode「104. Maximum Depth of Binary Tree」 まず初めに、numsが空だった場合にアーリーリターンでnullを返します。
そして後程作成するメソッドにデータと中央を割り出すための範囲を渡して再帰的な処理を開始します。
public TreeNode SortedArrayToBST(int[] nums)
{
// エラー処理
if (nums.Length == 0)
{
return null;
}
// 再帰的な処理を開始
return CreateBSTWithDFS(nums, 0, nums.Length - 1);
}作成するメソッドは「指定された範囲の真ん中をノードとして作成し、作成したノードから左右にノードを作成する」という処理を実装します。
データがない場合はエラー処理として事前に書いたので範囲が正常でない場合はnullを返す処理を書きます。
public TreeNode CreateBSTWithDFS(int[] nums, int low, int high)
{
if (low > high)
{
return null;
}
}次に渡された2つのインデックスから中央のインデックスを求め、値からノードを作成します。
public TreeNode CreateBSTWithDFS(int[] nums, int low, int high)
{
if (low > high)
{
return null;
}
// 中央のインデックスを求めてノードを作成
int mid = low + (high - low) / 2;
// int mid = Convert.ToInt32(low + Math.Ceiling((double)(high - low)/2));
var node = new TreeNode(nums[mid]);
}int mid = low + (high - low) / 2;を使用して中央値を求めると0,1など整数で割り切れない場合は切り捨てられるため、以下のような図になります。
これでも問題ありませんが、以下のようにきれいにツリーを作成したい場合は切り上げとするこのような計算式にしてください。int mid = Convert.ToInt32(low + Math.Ceiling((double)(high - low) / 2));
今回は速度を優先するため処理の少ない前者の計算式を使用します。
中央値のノードを作成したら左右を伸ばしていくためノードを作成できるかデータと中央を除外した低い範囲と高い範囲をそれぞれ再帰的に実行します。
最後に中央値のノードを作成して完成です。
public TreeNode CreateBSTWithDFS(int[] nums, int low, int high)
{
if (low > high)
{
return null;
}
// 中央のインデックスを求めてノードを作成
//int mid = Convert.ToInt32(low + Math.Ceiling((high - low) / (double)2));
int mid = low + (high - low) / 2;
var node = new TreeNode(nums[mid]);
// 左右のノードを求める
node.left = CreateBSTWithDFS(nums, low, mid - 1);
node.right= CreateBSTWithDFS(nums, mid + 1, high);
return node;
}ソースコード
public class Solution {
public TreeNode SortedArrayToBST(int[] nums)
{
// エラー処理
if (nums.Length == 0)
{
return null;
}
return CreateBSTWithDFS(nums, 0, nums.Length - 1);
}
public TreeNode CreateBSTWithDFS(int[] nums, int low, int high)
{
if (low > high)
{
return null;
}
// 中央のインデックスを求めてノードを作成
//int mid = Convert.ToInt32(low + Math.Ceiling((double)(high - low) / 2));
int mid = low + (high - low) / 2;
var node = new TreeNode(nums[mid]);
// 左右のノードを求める
node.left = CreateBSTWithDFS(nums, low, mid - 1);
node.right= CreateBSTWithDFS(nums, mid + 1, high);
return node;
}
}