バイナリサーチツリー検証問題解決チュートリアル:3つのソリューションの完全比較 | LeetCode 98 ベストプラクティス

LeetCode 98のValidate Binary Search Tree問題の解法を示す図

この記事では、LeetCode 98「Validate Binary Search Tree」の解答を、問題解決のアプローチやアルゴリズムの手順から時間計算量や空間計算量まで、完全に解説します。また、境界ケースをまとめ、3つの解答を比較することで、「Validate Binary Search Tree」を基礎から理解するのに役立ちます。

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 4 ].
  • -2 31 <= ノード値 <= 2 31 - 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))
				
			

二分探索木の検証問題の解決策

最もよくある間違いは、「左手」だけをチェックすることです。 <親子関係 「< 右の子」は、局所的な正しさを保証するだけで、「深いノードが祖先の範囲を逸脱する」状況を検出することはできません。正しいアプローチは、再帰中に開区間(下限、上限)を渡すことです。左に進むにつれて上限を狭め、右に進むにつれて下限を狭め、ノードの値は厳密にその区間内に収まる必要があります。

検証バイナリサーチツリーアルゴリズムの手順

  1. validate(node, low, high) を定義し、最初の呼び出しでは負の無限大と正の無限大が渡されます。
  2. ノードがnullの場合(空のツリーも有効)はtrueを返します。
  3. node.valがオープン区間(low、high)内にない場合は、falseを返します。
  4. 有効な操作では、左に戻る際に `(low, node.val)` と `(node.val, high)` の両方が真である必要があります。

検証バイナリーサーチツリーの複雑性分析

プロジェクト複雑
時間計算量の上)
空間の複雑さおお)

各ノードは正確に一度だけ訪問され、時間計算量はO(n)です。空間計算量は、再帰スタックの深さに対してO(h)、平衡木に対してO(log n)、縮退チェーンに対してO(n)です。中順走査バージョンも同じ計算量です。

二分探索木の検証における境界ケースと一般的なエラー

  • 厳密な不等式を使用する必要があり、二分探索木では一般的に重複する値は許可されません。
  • 境界値は整数の極値と等しくなる可能性があるため、INT_MIN を使用するよりも、言語の無限型または null 許容型を使用する方が安全です。
  • 親子関係のみを比較するのは最もよくある間違いです。常に範囲伝播を使用してください。
  • 空のツリーと単一ノードのツリーはどちらもtrueを返すはずです。

二分探索木を検証するための他のソリューションとの比較

解法時間空間例示する
父子関係のみをチェックするの上)おお)一般的に誤解されている解決策では、根深い違反行為を検出できない。
中間訪問や検査は、本当に増加傾向にあるのでしょうか?の上)おお)これも正しいです。以前の値を保存する必要があります。
レンジパス再帰の上)おお)この記事では