概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
問題
98. Validate Binary Search Tree
二分木のルートが与えられたとき、それが有効な二分木探索木（BST）であるかどうかを判断せよ。
有効なBSTは以下のように定義される。
- ノードの左サブツリーには、そのノードのキーより小さいキーを持つノードのみが含まれる
- ノードの右サブツリーには、そのノードのキーより大きいキーを持つノード が含まれる
- 左右のサブツリーの両方が二分探索木でなければならない。
制約
- ツリーのノード数は
[1, 104]の範囲 -231 <= Node.val <= 231 - 1
解説
この問題はすべてのノードを確認する必要があるので、DFSもしくはBFSを使用して探索を行う必要があります。
問題の有効な二分探索木をよく見ると『左から順に値が昇順になっている』ことが分かります。またこの『左から順に』というところに着目するとDFSの探索と同じ流れになっているので、今回はDFSを実装して問題を解決していきます。
初めにDFS探索を行うメソッドを実行します。
この際二分探索木の条件として値が範囲内かを確認しなければならないので上限と下限となる値を渡します。
IsValidBST
public bool IsValidBST(TreeNode root)
{
// DFS探索を開始して各ノードの構成が二分探索木になっているか
return IsValidBSTWithDFS(root, long.MinValue, long.MaxValue);
}では早速DFS探索の処理を実装していきましょう。
まずはノードがnullだった場合は二分探索木ではないのでfalseを返します。
次に対象のノードが指定範囲内かどうかを判定します、範囲外であれば二分探索木の条件を満たさないのでfalseを返します。
最後にサブツリーが二分探索木かどうかを再帰的に判定させて終了です。
その際、左のサブツリーには範囲を自分未満に設定し右のサブツリーには範囲を自分よりも高い判定にしましょう。
IsValidBST
public bool IsValidBSTWithDFS(TreeNode node, long min, long max)
{
// nullであれば二分探索木ではない
if (node is null)
{
return true;
}
// 値が範囲内かどうか
if(node.val >= max || node.val <= min)
{
return false;
}
// サブツリーが二分探索木かどうか
return IsValidBSTWithDFS(node.left, min, node.val) && IsValidBSTWithDFS(node.right, node.val, max);
}ソースコード
Solution.cs
public class Solution {
public bool IsValidBST(TreeNode root)
{
// DFS探索を開始して各ノードの構成が二分探索木になっているか
return IsValidBSTWithDFS(root, long.MinValue, long.MaxValue);
}
public bool IsValidBSTWithDFS(TreeNode node, long min, long max)
{
if (node is null)
{
return true;
}
if(node.val >= max || node.val <= min)
{
return false;
}
return IsValidBSTWithDFS(node.left, min, node.val) && IsValidBSTWithDFS(node.right, node.val, max);
}
}