概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
問題
104. Maximum Depth of Binary Tree
二分木の根が与えられたとき、その最大深度を返す。
二分木の最大深度は、ルートノードから最遠のリーフノードまでの最長経路に沿ったノードの数である。
制約
- ツリーのノード数は、
[0, 104]の範囲である。 -100 <= Node.val <= 100
解説
二分木の構成は左右のノードの有無はありますが常に二つに枝分かれする構成になっています。
左右の枝の深さを比較し、深い方を選択して自分の数を足す。
この処理をすべてのノードで繰り返し行うことで最終的に最も深い枝の深さが求められます。
確認処理は、DFS(深さ優先探索)で再帰的に実行します。
ここで流れをイメージするために再帰的に実行したらどうなるか追いかけてみましょう。
まず最初は二分木の根元を表すrootが渡されますので、DFSで探索をかけます。
再帰的に実行しますが青丸で最後までたどり着いたので、再度実行はせずに一つ上に戻ります。
この戻る際に枝を比較して大きい方の数に自分を足して数を数えていきます。
両方とも枝はないので0+1となり、青丸のから先の最大深さは1となります。
この処理を繰り返していき遡りながら数えていくことで最終的に一番深い枝の深さが求められます。
ソースコード
Solution.cs
public class Solution {
public int MaxDepth(TreeNode root) {
if(root == null)
{
return 0;
}
int maxLeft = MaxDepth(root.left);
int maxRight = MaxDepth(root.right);
return Math.Max(maxLeft, maxRight) + 1;
}
}