[Leetcode] 0098. 二分探索木の検証

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

与えられた 根 二分木の 有効な二分探索木（BST）であるかどうかを判断する.

あ 有効なBST は次のように定義されます。

ノードの左サブツリーにはキーを持つノードのみが含まれる未満ノードのキー。
ノードの右サブツリーにはキーを持つノードのみが含まれる より大きい ノードのキー。
左と右のサブツリーも両方ともバイナリ検索ツリーである必要があります。

例 1:

入力： ルート = [2,1,3]
出力： 真実

例 2:

入力： ルート = [5,1,4,null,null,3,6]
出力： 間違い
説明： ルート ノードの値は 5 ですが、その右の子の値は 4 です。

制約:

ツリー内のノードの数は範囲内です [1, 10 ⁴ ].
-2 ³¹ <= ノード値 <= 2 ³¹ - 1

パイソン

				
					# 時間計算量: O(n) # 空間計算量: O(n) import math from entering import Optional class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class ソリューション: def isValidBST(self, root: Optional[TreeNode]) -> bool: def dfs(node: Optional[TreeNode], low=-math.inf, high=math.inf): if node is None: return True if node.val <= low: return False if node.val >= high: return False return dfs(node.left, low, node.val) and dfs(node.right, node.val, high) return dfs(root) class ソリューション: def isValidBST(self, root: Optional[TreeNode]) -> bool: prev = [-math.inf] def dfs(node: Optional[TreeNode], prev): ノードでない場合: True を返す dfs(node.left, prev): False を返す node.val <= prev[0] の場合: False を返す prev[0] = node.val を返す dfs(node.right, prev) を返す dfs(root, prev) root1 = TreeNode(2) root1.left = TreeNode(1) root1.right = TreeNode(3) print(Solution().isValidBST(root1)) root2 = TreeNode(5) root2.left = TreeNode(1) root2.right = TreeNode(4) root2.right.left = TreeNode(3) root2.right.right = TreeNode(6) print(Solution().isValidBST(root2))

パイソン

関連記事