二叉树查找的递归匹配实现方案对比及合理性问询

你的代码核心问题是不会在左子树搜索失败后回溯去搜索当前节点的右子树，这会导致大量漏搜场景——即使目标节点存在于右子树中，你的代码也可能找不到它。

反例验证 #

假设我们有这样的二叉树：

let test_tree = Node(1, Node(2, Empty, Empty), Node(3, Empty, Empty))

当调用你的search 3 test_tree时：

1. 根节点1≠3，进入第三个分支，左子树非空，递归搜索左子树Node(2, Empty, Empty)
2. 左子树根节点2≠3，进入第三个分支，左子树为空，递归搜索该节点的右子树Empty
3. 返回Empty，函数直接结束，完全不会去搜索原根节点的右子树Node(3, Empty, Empty)

而另一套实现会在左子树搜索返回Empty后，继续递归搜索右子树，最终找到目标节点。

两者的逻辑差异 #

• 你的代码：仅在当前节点左子树为空时才搜索右子树，一旦左子树非空就只递归左子树，完全忽略上层节点的右子树
• 正确实现：先递归搜索左子树，若左子树无结果，再递归搜索右子树，保证遍历所有节点，符合O(n)时间复杂度的要求

关于高效性和可读性的误解 #

1. 高效性：你的代码看似少了一次匹配，但本质是逻辑残缺，连基本的搜索功能都无法完成。即使不考虑正确性，两者在最坏情况下的时间复杂度都是O(n)，没有效率优势。
2. 可读性：正确实现的逻辑更贴合二叉树遍历的常规思路（左→右），结构清晰；你的代码额外嵌套了一层match，反而容易混淆遍历逻辑，增加理解成本。

修正你的实现 #

如果想保持类似的结构，需要确保左子树搜索失败后去搜索右子树，示例如下：

let rec search x tree = 
  match tree with 
  | Empty -> Empty
  | Node (root, left, right) when x = root -> tree
  | Node (_, left, right) ->
    let left_result = search x left in
    if left_result <> Empty then left_result
    else search x right

内容的提问来源于stack exchange，提问作者v_head