NeetCode 150 [Trees]medium:Validate Binary Search Tree

NeetCodeのSolutionを書いていく

Validate Binary Search Tree

問題

２分木のルートが与えられます。
２分探索木が有効なら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