ゼロから始めるLeetCode Day107「98. Validate Binary Search Tree」

• 概要
• 問題
• 解法

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day106「209. Minimum Size Subarray Sum」

次回
ゼロから始めるLeetCode Day108「300. Longest Increasing Subsequence」

Twitterやってます。

問題

98. Validate Binary Search Tree
難易度はMedium。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、二分木が与えられた場合，それが有効な二分探索木(Binary Search Tree)であるかどうかを判断してください、というものです。

なお、二分探索木は以下のように定義されているとします。

• ノードの左の木には、そのノードの値よりも小さい値を持つノードのみが含まれます。

• ノードの右の木には、そのノードの値よりも大きい値を持つノードのみが含まれます。

• 左の木と右の木の両方が二分探索木でなければなりません。

解法

# 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: TreeNode) -> bool:
        low,high = float("-inf"),float("inf")
        def helper(node,low,high):
            if not node:
                return True
            val = node.val
            if val <= low or val >= high:
                return False
            
            if not helper(node.left,low,val):
                return False
            if not helper(node.right,val,high):
                return False
            return True
        return helper(root,low,high)
# Runtime: 44 ms, faster than  83.89%  of  Python3  online submissions for  Validate Binary Search Tree.
# Memory Usage: 16.2 MB, less than  43.01%  of  Python3  online submissions for  Validate Binary Search Tree.

helper関数を使った再帰での実装です。
ノードの値とその上限値と下限値があれば比較する、という工程を左右の木に対して再帰的に繰り返す、というものです。

無限大を使った理由は前回でも説明した通りで、最大と最小の値を判定する時に使うからです。

では今回はここまで。
お疲れ様でした。