概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
問題
二分木のrootと整数のtargetSumが与えられたとき、その木がルートからリーフノードへのパスを持ち、そのパスに沿ったすべての値の合計がtargetSumに等しい場合に真を返す。
リーフとは、子を持たないノードのことである。
制約
- ツリーのノード数は
[0, 5000]の範囲 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
解説
与えられたrootノードからリーフノードまでのパスをたどり、指定された合計値になるかどうかを判定する問題です。
DFSを使用した問題ですので、DFSに慣れていない方はまずはこちらの問題から解くことをお勧めします。
C#で解くLeetCode「104. Maximum Depth of Binary Tree」 まず初めに、rootがnullかどうかを確認し、nullであれば必ず一致しないのでfalseとするエラー処理を書きましょう
HasPathSum
public bool HasPathSum(TreeNode node, int targetSum)
{
if (node == null)
{
return false;
}
}次に問題文にはリーフノードへのパスを検索するので、リーフノードであれば渡された数が一致しているか判定を行います。
HasPathSum
public bool HasPathSum(TreeNode node, int targetSum)
{
if (node == null)
{
return false;
}
if (node.left is null && node.right is null)
{
return node.val == targetSum;
}
}最後にDFS探索を行うために現在のノードの左右に同じメソッドを実行します。
指定された合計値から現在の値を差し引いた数を渡して、合計値が一致するかを確認するDFS探索をして終了です。
HasPathSum
public bool HasPathSum(TreeNode node, int targetSum)
{
if (node == null)
{
return false;
}
if (node.left is null && node.right is null)
{
return node.val == targetSum;
}
return HasPathSum(node.left, targetSum - node.val) || HasPathSum(node.right, targetSum - node.val);
}ソースコード
Solution.cs
public class Solution {
public bool HasPathSum(TreeNode node, int targetSum)
{
if (node == null)
{
return false;
}
if (node.left is null && node.right is null)
{
return node.val == targetSum;
}
return HasPathSum(node.left, targetSum - node.val) || HasPathSum(node.right, targetSum - node.val);
}
}