概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
問題
105. Construct Binary Tree from Preorder and Inorder Traversal
2つの整数配列preorderとinorderが与えられた際二分木を構築して返せ。preorderは二分木の前置走査、inorderは同じ二分木の順序走査を表す。
制約
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorderとinorderは一意な値で構成される。inorderの各値はpreorderにも現れる。preorderは、前置走査であることが保証される。inorderは木の探索の順序が逆であることが保証されている。
解説
まずは渡された配列を再帰的に実行する処理に渡します。
その際、第一引数にはrootを表すpreorderのインデックス『0』を渡します。第二引数と第三引数にはinorderの使用する範囲を渡します。一番最初の実行なのですべての範囲を渡しましょう。
public TreeNode BuildTree(int[] preorder, int[] inorder)
{
return BuildTree(0, 0, inorder.Length - 1, preorder, inorder);
}次に渡した情報から二分木を生成する再帰的な処理を実装します。
まず初めに、渡されたインデックスが異常だったり、探索範囲が外れたらnullを返します。
そして渡されたpreorderとpreStartIndexからノードを作成します。
public TreeNode BuildTree(
int preStartIndex,
int inStartIndex,
int inEndIndex,
int[] preorder,
int[] inorder)
{
// 探索範囲が範囲外であればnullを返す
if (preStartIndex > preorder.Length - 1 || inStartIndex > inEndIndex)
{
return null;
}
// 渡された範囲とデータからルートになるノードを探す
var node = new TreeNode(preorder[preStartIndex]);
}次に後程サブツリーに渡すデータを左右に分割するため、現在のノードがinorderで指定された範囲の何番目かを数えます。inorderの開始位置と終了位置の範囲にノードがあるはずなので、インデックスを使用して処理を省きます。
そして再帰的な処理で左右のサブツリーを生成します。渡す『サブツリーのrootとなるインデックス』と『サブツリーに使用する値の範囲』左に渡す値はを渡します。
左にはpreStartIndex + 1とinStartIndex & inIndex - 1を渡します。
右に渡す位置はpreStartIndex + inIndex - inStartIndex + 1とinIndex + 1 & inEndIndex
public TreeNode BuildTree(
int preStartIndex,
int inStartIndex,
int inEndIndex,
int[] preorder,
int[] inorder)
{
...
// 現在のノードがinorderの何番目かを探し出す
int inIndex = 0;
for (int i = inStartIndex; i <= inEndIndex; i++)
{
if (inorder[i] == node.val)
{
inIndex = i;
}
}
// preStartIndexは左のrootのインデックスを指定
// inorderのインデックスは開始位置から現在のノードの左までの範囲を指定
node.left = BuildTree(
preStartIndex + 1,
inStartIndex,
inIndex - 1,
preorder,
inorder);
// preStartIndexは右のrootのインデックスを指定
// inorderのインデックスは現在のノードから終了位置の範囲を指定
node.right = BuildTree(
preStartIndex + inIndex - inStartIndex + 1,
inIndex + 1,
inEndIndex,
preorder,
inorder);
return node;
}ソースコード
public TreeNode BuildTree(
int preStartIndex,
int inStartIndex,
int inEndIndex,
int[] preorder,
int[] inorder)
{
// 探索範囲が範囲外であればnullを返す
if (preStartIndex > preorder.Length - 1 || inStartIndex > inEndIndex)
{
return null;
}
// 渡された範囲とデータからルートになるノードを探す
var node = new TreeNode(preorder[preStartIndex]);
// 現在のノードがinorderで指定された範囲の何番目かを探し出す
int inIndex = 0;
for (int i = inStartIndex; i <= inEndIndex; i++)
{
if (inorder[i] == node.val)
{
inIndex = i;
}
}
// preStartIndexは左のrootのインデックスを指定
// inorderのインデックスは開始位置から現在のノードの左までの範囲を指定
node.left = BuildTree(
preStartIndex + 1,
inStartIndex,
inIndex - 1,
preorder,
inorder);
// preStartIndexは右のrootのインデックスを指定
// inorderのインデックスは現在のノードから終了位置の範囲を指定
node.right = BuildTree(
preStartIndex + inIndex - inStartIndex + 1,
inIndex + 1,
inEndIndex,
preorder,
inorder);
return node;
}