Go语言BST中序递归遍历两种写法结果差异原因咨询

问题背景 #

编写二叉搜索树（BST）中序遍历逻辑时遇到异常：仅做了极小幅的语法调整代码就返回正确结果，但最初版本无法正常工作的原因始终无法定位。两段代码原本被认为运行逻辑完全一致，实际输出结果存在明显差异。

两种写法的核心区别：

• 错误写法：先将curr变量赋值为其左节点curr.left，再递归调用InOrderRecursive方法
• 正确写法：直接在curr.left节点上调用InOrderRecursive方法，不修改当前作用域的curr指向

基础定义 #

BST结构体 #

type BST struct {
    value int
    left *BST
    right *BST
}

错误版本（可运行但返回值错误） #

func (tree *BST) InOrderRecursive(values []int) []int {
    curr := tree

    if curr.left != nil {
        curr = curr.left
        values = curr.InOrderRecursive(values)
    }
    values = append(values, curr.value)
    if curr.right != nil {
        curr = curr.right
        values = curr.InOrderRecursive(values)
    }
    return values
}

正确版本（返回符合预期的遍历结果） #

func (tree *BST) InOrderRecursive(values []int) []int {
    curr := tree

    if curr.left != nil {
        values = curr.left.InOrderRecursive(values)
    }
    values = append(values, curr.value)
    if curr.right != nil {
        values = curr.right.InOrderRecursive(values)
    }
    return values
}

两段代码行为不一致的核心原因是：错误版本非法修改了当前函数作用域内curr的指针指向，导致后续遍历逻辑的操作节点完全偏离预期。

中序遍历的标准执行顺序固定为：递归遍历左子树 -> 追加当前节点值 -> 递归遍历右子树，整个流程中当前函数作用域对应的「当前处理节点」不能被随意篡改。

1. 错误版本在处理左子树分支时，执行curr = curr.left，直接将当前作用域内原本指向当前节点的curr指针，重定向到了左子节点。等左子树的递归调用全部完成回到当前作用域后，后续逻辑操作的已经不是原本要处理的当前节点：
   • 执行append(values, curr.value)时，追加的是左子节点的值，而非当前节点的值，直接造成值重复、节点遗漏
   • 后续处理右子树时，判断的是被修改后的curr（即左子节点）的右指针，完全跳过了原当前节点的整棵右子树，遍历路径彻底错乱
2. 正确版本从未修改当前作用域的curr指向：调用curr.left.InOrderRecursive(values)时，仅将左子节点作为方法接收者传入递归调用，当前作用域下的curr始终指向最初的当前节点。递归返回后，追加的是正确的当前节点值，后续遍历右子树时也是读取原当前节点的右指针，完全匹配中序遍历的逻辑要求。

以最简单的三层节点BST为例验证：根节点值为2，左子节点值为1，右子节点值为3。

• 正确版本执行后输出[1,2,3]，符合中序遍历结果
• 错误版本执行时，进入根节点作用域后先将curr修改为指向左子节点1，递归遍历完1的子树（追加1）后，会再次追加curr（即1）的值，之后判断1的右子节点为空直接返回，最终输出[1,1]，完全漏掉根节点2和右子节点3，和实际错误表现完全一致。

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