BST 經典問題#
驗證二元搜尋樹 (LeetCode 98)#
解法一：中序走訪#
核心原理：BST 的中序走訪結果必為嚴格遞增序列。
def isValidBST(root):
prev = float('-inf')
def inorder(node):
nonlocal prev
if not node:
return True
if not inorder(node.left):
return False
if node.val <= prev: # 不是嚴格遞增
return False
prev = node.val
return inorder(node.right)
return inorder(root)空間優化：不需存整個走訪序列，只需維護「前一個節點值」即可。
解法二：遞迴區間驗證#
傳遞允許的數值範圍 (min, max)：
def isValidBST(root):
def validate(node, min_val, max_val):
if not node:
return True
if node.val <= min_val or node.val >= max_val:
return False
return (validate(node.left, min_val, node.val) and
validate(node.right, node.val, max_val))
return validate(root, float('-inf'), float('inf'))最近公共祖先 (LeetCode 235/236)#
普通二元樹 (LeetCode 236)#
使用後序走訪，自底向上回傳：
def lowestCommonAncestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right: # p, q 分居兩側
return root
return left if left else right精髓：回傳值具有多重含義 - 既表示「找到了 p 或 q」，也表示「找到了 LCA」。
BST 版本 (LeetCode 235)#
利用 BST 的排序特性，迭代實現：
def lowestCommonAncestor(root, p, q):
while root:
if p.val < root.val and q.val < root.val:
root = root.left # 都在左邊
elif p.val > root.val and q.val > root.val:
root = root.right # 都在右邊
else:
return root # 分岔點即為 LCA
return None優勢：BST 版本可用迭代，空間複雜度 O(1)。
二元樹的深度 (LeetCode 104/111)#
最大深度#
def maxDepth(root):
if not root:
return 0
return max(maxDepth(root.left), maxDepth(root.right)) + 1最小深度#
陷阱：不能直接
min(left, right) + 1！單邊子樹為空時不算葉節點。
def minDepth(root):
if not root:
return 0
left = minDepth(root.left)
right = minDepth(root.right)
# 處理單邊子樹為空的情況
if left == 0 or right == 0:
return left + right + 1
return min(left, right) + 1