BST节点定义为包含val、left、right属性的TreeNode类，插入需递归比较并返回新根以维护全局有序性，search应返回节点而非布尔值。
如何定义 BST 节点并保证左右子树有序
BST 的核心约束是：对任意节点 node，其左子树所有节点值都 node.val，右子树所有节点值都 > node.val。这意味着插入和查找必须严格遵循该规则，不能只比父节点判断——比如插入 5 到以 10 为根、左子节点为 3 的树中，若直接挂在 3 右侧，就可能违反全局有序性（例如 3 右侧已有 8，而 5 插入后仍合法；但若误插到 10 左侧的任意位置而不递归比较，就容易出错）。
所以节点定义要支持递归操作：
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
- 不要在初始化时做大小校验——校验逻辑属于插入过程，不是构造职责
-
left和right默认为None，避免插入时意外传入未初始化对象 - 不建议用字典或
dataclass替代——虽然可行，但会模糊“树结构需显式指针”的语义，后续递归易出错
insert 方法必须递归下降且只在叶节点插入
常见错误是写成「找到空位就停」但没处理回溯赋值，导致新节点无法挂到父节点上。正确做法是让 insert 返回当前子树的新根（可能是原节点，也可能是新节点），由上层决定赋给 left 或 right。
示例实现：
立即学习“Python免费学习笔记（深入）”；
def insert(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert(root.left, val)
elif val > root.val: # 注意：跳过重复值，BST 通常不允许重复
root.right = insert(root.right, val)
return root
- 必须用
val < root.val和val > root.val分开判断，不能合并成else——否则重复值会被错误插入左或右，破坏唯一性 - 如果业务允许重复值，需明确策略：统一放右？加计数字段？不能靠模糊的
else隐含处理 - 非递归写法虽可行，但需手动维护栈或 parent 指针，出错率高；初学阶段坚持递归更安全
search 方法返回节点而非布尔值更实用
单纯返回 True/False 在实际开发中价值有限。多数场景需要拿到匹配节点本身——比如删除时要找前驱/后继，或者修改其关联数据。因此 search 应返回 TreeNode 或 None。
def search(root, val):
if not root or root.val == val:
return root
if val < root.val:
return search(root.left, val)
return search(root.right, val)
- 检查
root.val == val必须放在not root之后，否则空节点调用.val会抛AttributeError - 不要在递归调用后加额外判断（如
if result: return result）——上面写法已保证单路径返回，冗余逻辑反而增加理解负担 - 若需支持范围查询（如找所有
[low, high]内的值），就不能用这个单值search，得另写中序遍历剪枝版本
测试时最容易漏掉的边界情况
新手常只测「正常插入+查找」，但真实 BST 行为在边界上很敏感。以下三类必须覆盖：
- 空树插入：
insert(None, 5)→ 应返回新节点，不是报错或静默失败 - 重复值插入：
insert(insert(None, 3), 3)→ 根应仍是3，左右子树保持None，不能多出一个节点 - 单边链状树查找：
search(链状右斜树, 极大值)→ 会递归到最深叶子再返回None，别因超时或栈溢出就误判逻辑错（Python 默认递归限制约 1000 层，建千级链需手动调sys.setrecursionlimit）
这些不是“特殊情况”，而是 BST 定义本身决定的必经路径。少验证一条，上线后就可能在某个用户数据分布下暴露逻辑裂缝。
