概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
問題
2つの二分木が与えられるので2つをマージし、マージされた二分木を返せ。
2つのノードが重なっている場合、合計値を新しい値とする。
片方のノードしか存在しない場合はその値を引き継ぐ。
どちらにもノードが存在していない場合はnullとする。
注意: マージ処理は、両方の木のルートノードから開始しなければならない。
制約
- 二つの二分木のノード数は
[0, 2000]の範囲である。 -104 <= Node.val <= 104
解説
2つの二分木を合わせて新しい二分木を作成する問題です。
全てのノードを探索する必要があるため、DFSで探索しながら新しい二分木を作成します。
（BFSでも可能ですが、DFSは再帰的な関数を作成して少ないコード量で表せられるため今回はDFSを選択しました）
再帰的なDFSを使用した簡単な問題はこちらにもあるので、まずはこちらを先に解くことをお勧めいたします。
C#で解くLeetCode「104. Maximum Depth of Binary Tree」 まず初めに、両方がnullだった場合はnullを返すのでアーリーリターンでnullを返します。
private TreeNode MergeTrees(TreeNode node1, TreeNode node2)
{
// どちらも null であれば null を返す
if (node1 is null && node2 is null)
{
return null;
}
}次に合計値を求めて新しいノードを作成します。
さきほどアーリーリターンでどちらもnullだった場合を返しているので、ここを通るのは「少なくともどちらかは存在している」ということになります。
private TreeNode MergeTrees(TreeNode node1, TreeNode node2)
{
// どちらも null であれば null を返す
if (node1 is null && node2 is null)
{
return null;
}
// 合計した新しいノードを作成
var newNode = new TreeNode(
(node1 == null ? 0 : node1.val) +
(node2 == null ? 0 : node2.val));
}この際、node1, node2にはnullが来るパターンがあることを忘れないでください。node1.val + node2.valのようにするとnode1, node2のどちらかがnullだった場合nullを参照することになるので例外が発生します。
なので、「nullだった場合は0を足す、nullじゃなければそのまま足す」という書き方にして合計を割り出します。
そして、左右のノードを作成するため再帰的に同じメソッドを実行します。
最後に作成したノードを返して再帰的なDFS処理を使用した二分木マージ処理の完成です。
private TreeNode MergeTrees(TreeNode node1, TreeNode node2)
{
// どちらも null であれば null を返す
if (node1 is null && node2 is null)
{
return null;
}
// 合計した新しいノードを作成
var newNode = new TreeNode(
(node1 == null ? 0 : node1.val) +
(node2 == null ? 0 : node2.val));
// 左右のノードを作成
newNode.left = MergeTrees(
node1 == null ? null : node1.left,
node2 == null ? null : node2.left);
newNode.right = MergeTrees(
node1 == null ? null : node1.right,
node2 == null ? null : node2.right);
return newNode;
}ソースコード
public class Solution {
public TreeNode MergeTrees(TreeNode node1, TreeNode node2) {
// どちらも null であれば null を返す
if (node1 is null && node2 is null)
{
return null;
}
var newNode = new TreeNode(
(node1 == null ? 0 : node1.val) +
(node2 == null ? 0 : node2.val));
newNode.left = MergeTrees(
node1 == null ? null : node1.left,
node2 == null ? null : node2.left);
newNode.right = MergeTrees(
node1 == null ? null : node1.right,
node2 == null ? null : node2.right);
return newNode;
}
}