驗證二元搜尋樹
“驗證 BST”問題的詳細指南和 Python 實作。
1. 學習
「驗證 BST」問題是樹部分的關鍵挑戰。
此實作著重於 Python 中的簡單層級邏輯。
在我們提供的解決方案中，我們優先考慮技術準確性和程式碼可讀性。
2. Real-World Applications
3. Visual Intuition
視覺化驗證 BST 的邏輯流程。
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
仔細閱讀驗證 BST 的問題陳述。
2. Formulate brute force
起草一個簡單的迭代解決方案。
3. Identify inefficiency
尋找冗餘計算。
4. Optimize search path
使用散列或排序來加速該過程。
5. Final Implementation
清理生產標準代碼。
問題陳述
給定二元樹的根，確定它是否是有效的二元搜尋樹（BST）。
有效的 BST 定義如下：
- 節點的左子樹僅包含鍵嚴格小於該節點鍵的節點。
- 節點的右子樹僅包含鍵嚴格大於該節點鍵的節點。
- 左右子樹也必須是二元搜尋樹。
該樹被表示為一個級別順序列表。實作函數 isValidBST(root: list) -> bool。
- •The number of nodes in the tree is in the range [1, 10000]
- •-2^31 <= Node.val <= 2^31 - 1
範例
[2,1,3]
True
The left child 1 < root 2, and right child 3 > root 2. Valid BST.
[5,1,4,None,None,3,6]
False
The right child of root is 4, which is less than 5. Also, node 3 is in the right subtree of 5 but is less than 5. Not a valid BST.
[5,4,6,None,None,3,7]
False
Node 3 is in the right subtree of 5 but has value 3 < 5. Not valid.
Need a Hint?
Edge Cases to Watch
- 空輸入結構
- 單元素輸入
- 大數值範圍
準備好解決了嗎？
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
面試見解和變化
複雜度分析分解
為什麼時間: Directly evaluates all possibilities.
為什麼選擇太空: Uses standard local memory.
為什麼時間: Optimized paths reduce total operations.
為什麼選擇太空: May trade memory for speed.
最佳化解決方案Python程式碼
最佳化解決方案Python程式碼
def is_valid_bst_opt(root):
if isinstance(root, list):
r = build_tree(root)
return is_valid_bst_opt_helper(r)
return is_valid_bst_opt_helper(root)
def is_valid_bst_opt_helper(root: TreeNode) -> bool:
def validate(node, low, high):
if not node:
return True
if not (low < node.val < high):
return False
return validate(node.left, low, node.val) and validate(node.right, node.val, high)
return validate(root, float('-inf'), float('inf'))暴力破解代碼（劇透保護）
暴力破解代碼（劇透保護）
def is_valid_bst_brute(root):
if isinstance(root, list):
r = build_tree(root)
return is_valid_bst_brute_helper(r)
return is_valid_bst_brute_helper(root)
def is_valid_bst_brute_helper(root: TreeNode) -> bool:
vals = []
def inorder(node):
if not node: return
inorder(node.left)
vals.append(node.val)
inorder(node.right)
inorder(root)
for i in range(len(vals) - 1):
if vals[i] >= vals[i + 1]:
return False
return TrueAlgorithm Pattern Checklist
When dealing with Trees data patterns.
- Are constraints clear?
- Is there a linear or logarithmic optimization possible?
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
推薦的 Python 資源
透過相關的互動式教學、備忘單和程式碼比較來擴展您的知識。
Python 迴圈：For 與 While 迴圈解釋
了解如何使用 Python 循環來迭代資料。透過互動式範例掌握 for 迴圈、while 迴圈、break、continue 和迴圈最佳實務。
如何在 Python 中對列表進行排序（升序和降序）
了解如何在 Python 中使用 sort() 方法和sorted() 函數對清單進行排序。發現自訂鍵排序和逆序範例。
Python 字串方法備忘單
Python 字串操作的完整參考指南。掌握格式化、搜尋、拆分、取代和檢查字串屬性。
Python 與 JavaScript：哪種程式語言最好？
Python 和 JavaScript 的全面比較。探索語法差異、效能、用例（後端與前端）和編碼範例。