NeetCodeのSolutionを書いていく #
Validate Binary Search Tree #
https://neetcode.io/problems/valid-binary-search-tree
neetcode.io
問題 #
２分木のルートが与えられます。
２分探索木が有効ならtrueを無効ならfalseを返しましょう。
２分探索木が満たすべき特徴は以下です。
- 左側の全てのノードは自分自身よりもノードのkeyが小さいものしか持ちません
- 右側の全てのノードは自分自身よりもノードのkeyが大きいものしか持ちません
- 左側も右側も２分探索木である
例 #
Input: root = [2,1,3] Output: true
Input: root = [1,2,3] Output: false
制約 #
- 1 <= The number of nodes in the tree <= 1000.
- -1000 <= Node.val <= 1000
- 計算量：O(n)
- メモリ：O(n)
メモ #
深さ優先で再帰的にチェックをしていけば良い？ チェックするときにチェック対象の下限と上限の値を一緒に渡してチェックするのがポイント。
import collections
from typing import Optional
# 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:
if not root:
return True
# ここで最大、最小は無限を指定するのがポイント
q = collections.deque([(root, float("-inf"), float("inf"))])
while q:
node, minv, maxv = q.popleft()
if not (minv < node.val < maxv):
return False
if node.left:
q.append((node.left, minv, node.val))
if node.right:
q.append((node.right, node.val, maxv))
return True