【LeetCode】 98. Validate Binary Search Tree 解答・解説【Python】

はじめに
1. ポイント
2. この記事で得られること
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python, 深さ優先探索(Depth First Search)
終わりに
1. 補足・参考・感想
2. 疑問が解決した方は他の問題もどうぞ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

ポイント

- 二分探索木
- 深さ優先探索

この記事で得られること

- 二分探索木の概要
- 深さ優先探索の実装の練習

詳細

問題

原文

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

The left

subtree

of a node contains only nodes with keys less than the node’s key.

The right subtree of a node contains only nodes with keys greater than the node’s key.

Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [2,1,3] Output: true

1
2

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.

1
2
3

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].

-2³¹ <= Node.val <= 2³¹ - 1

内容(和訳)

二分木rootが与えられるので、二分探索木(binary search tree)であるかを判定してください。

BSTは以下の通りに定義されます。

左側の子孫ノードは、現ノードの値より小さい値を持つノードのみを含みます。

右側の子孫ノードは、現ノードの値より大きい値を持つノードのみを含みます。

左と右の子孫は、どちらも二分探索木でなければなりません。

※正しくない可能性があります。

解答

解答1：Python, 深さ優先探索(Depth First Search)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        return self.DFS(root, -inf, inf)

    #深さ優先探索。第一引数はノード、第二引数は低いはずの値、第三引数は高いはずの値
    def DFS(self, node, low, high):
        print(low,"low")
        print(high, "high")
        print("--------------")
        
        #ノードがなければTrueを返す。親ノードよりも大きい子ノードがないため。
        if not node: return True
        #親ノードと左右の子ノードの大小比較を行う
        if not (low < node.val < high):
            #二分探索木でなければFalse
            return False
        #左右の子ノードで再帰呼び出し。
        #左の子ではhighに現ノードの値、右の子ではlowに現ノードの値を入れて呼び出す。
        return self.DFS(node.left, low, node.val) and self.DFS(node.right, node.val, high)

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def isValidBST(self, root: Optional[TreeNode]) -> bool:

return self.DFS(root, -inf, inf)

#深さ優先探索。第一引数はノード、第二引数は低いはずの値、第三引数は高いはずの値

def DFS(self, node, low, high):

print(low,"low")

print(high, "high")

print("--------------")

#ノードがなければTrueを返す。親ノードよりも大きい子ノードがないため。

if not node: return True

#親ノードと左右の子ノードの大小比較を行う

if not (low < node.val < high):

#二分探索木でなければFalse

return False

#左右の子ノードで再帰呼び出し。

#左の子ではhighに現ノードの値、右の子ではlowに現ノードの値を入れて呼び出す。

return self.DFS(node.left, low, node.val) and self.DFS(node.right, node.val, high)

二分探索木の定義は問題に既に書かれていますがおさらいします。

あるノードの左側の子孫は、あるノードよりも小さい値のみを持ちます

あるノードの右側の子孫は、あるノードよりも大きい値のみを持ちます。

これが全てのノードに適用されます。

実装上は、深さ優先探索を行っています。

・根ノードからスタートして以下の操作をする関数を再帰的に呼び出しています。

ノードがなければTrueを返す。(親ノードが木の末端である葉ノードであるため)

左の子ノード＜現在のノード＜右の子ノード　の大小関係に沿っているかを判定

左の子ノードでこの関数を呼び出す。(高い方の引数には現在のノードの値を入れる)

右の子ノードでこの関数を呼び出す。(低い方の引数には現在のノードの値を入れる)

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

疑問が解決した方は他の問題もどうぞ

前：102. Binary Tree Level Order Traversal

次：1768. Merge Strings Alternately

LeetCode 解答・解説記事一覧