题目定位
DFS 最适合，因为 BST 的合法性依赖祖先给出的上下界，而不是局部父子比较。
关键观察
每个子树都会从祖先继承一个取值区间，节点必须严格落在该区间内。
目标复杂度
O(n) / O(h)
这题的解法思路怎么拆
1
DFS 最适合，因为 BST 的合法性依赖祖先给出的上下界，而不是局部父子比较。
2
每个子树都会从祖先继承一个取值区间，节点必须严格落在该区间内。
3
先识别图模型，并定义邻居如何生成。
4
无权最短路优先 BFS，结构搜索优先 DFS。
参考实现
Python# Generic pattern template
from collections import deque
def bfs(start):
queue = deque([start])
visited = {start}
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in visited:
visited.add(nxt)
queue.append(nxt)
def dfs(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs(nxt)
常见坑点
warning
只比较节点和它的直接孩子。
warning
边界写成包含式，错误地允许重复值。
高频追问
为什么中序遍历也能验证 BST？
为什么必须保留来自祖先的长程边界？
继续刷相关题
先把 BFS / DFS 这个模式刷成体系，再去做更难变体。