この記事では、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))
LeetCode問題拡張演習
同じシリーズの他の問題解決ノートも練習用としてお勧めします。
さらに詳しく知りたい方はこちらをご覧ください
二分探索木の検証問題の解決策
最もよくある間違いは、「左手」だけをチェックすることです。 <親子関係 「< 右の子」は、局所的な正しさを保証するだけで、「深いノードが祖先の範囲を逸脱する」状況を検出することはできません。正しいアプローチは、再帰中に開区間(下限、上限)を渡すことです。左に進むにつれて上限を狭め、右に進むにつれて下限を狭め、ノードの値は厳密にその区間内に収まる必要があります。
検証バイナリサーチツリーアルゴリズムの手順
- validate(node, low, high) を定義し、最初の呼び出しでは負の無限大と正の無限大が渡されます。
- ノードがnullの場合(空のツリーも有効)はtrueを返します。
- node.valがオープン区間(low、high)内にない場合は、falseを返します。
- 有効な操作では、左に戻る際に `(low, node.val)` と `(node.val, high)` の両方が真である必要があります。
検証バイナリーサーチツリーの複雑性分析
| プロジェクト | 複雑 |
|---|---|
| 時間計算量 | の上) |
| 空間の複雑さ | おお) |
各ノードは正確に一度だけ訪問され、時間計算量はO(n)です。空間計算量は、再帰スタックの深さに対してO(h)、平衡木に対してO(log n)、縮退チェーンに対してO(n)です。中順走査バージョンも同じ計算量です。
二分探索木の検証における境界ケースと一般的なエラー
- 厳密な不等式を使用する必要があり、二分探索木では一般的に重複する値は許可されません。
- 境界値は整数の極値と等しくなる可能性があるため、INT_MIN を使用するよりも、言語の無限型または null 許容型を使用する方が安全です。
- 親子関係のみを比較するのは最もよくある間違いです。常に範囲伝播を使用してください。
- 空のツリーと単一ノードのツリーはどちらもtrueを返すはずです。
二分探索木を検証するための他のソリューションとの比較
| 解法 | 時間 | 空間 | 例示する |
|---|---|---|---|
| 父子関係のみをチェックする | の上) | おお) | 一般的に誤解されている解決策では、根深い違反行為を検出できない。 |
| 中間訪問や検査は、本当に増加傾向にあるのでしょうか? | の上) | おお) | これも正しいです。以前の値を保存する必要があります。 |
| レンジパス再帰 | の上) | おお) | この記事では |


