为何Go语言之旅等价二叉树练习中，遍历改前/后序会出错？

这事儿我刚上手Go并发的时候也踩过一模一样的坑！核心问题出在你修改前序/后序遍历的时候，错误地给左右子树的递归遍历加上了go关键字，导致节点值发送到channel的顺序完全不可控。

先看为什么中序遍历能正常工作 #

你原来的中序遍历代码应该是这样的（没有额外启动goroutine）：

func Walk(t *tree.Tree, ch chan int) {
    if t != nil {
        Walk(t.Left, ch)
        ch <- t.Value
        Walk(t.Right, ch)
    }
}

整个遍历过程是在同一个goroutine里同步执行的——从左子树到根节点再到右子树，节点值严格按照中序顺序发送到channel，没有任何并发干扰。两棵相同的树会生成完全一致的序列，Same函数只要逐位比较就能正确判断等价性。

前序/后序出错的原因 #

如果你改成前序的时候写了类似这样的代码：

// 错误的前序遍历实现！
func Walk(t *tree.Tree, ch chan int) {
    if t != nil {
        ch <- t.Value
        go Walk(t.Left, ch)  // 启动goroutine遍历左子树
        go Walk(t.Right, ch) // 再启动一个goroutine遍历右子树
    }
}

麻烦就来了：左子树和右子树的遍历是两个独立的goroutine，Go的调度器会随机调度它们的执行顺序。哪怕是两棵完全相同的树，这两个goroutine的执行节奏也可能不一样——比如第一次左子树先发3个值，第二次右子树先发2个值，导致channel里的序列顺序混乱，Same函数自然会认为两棵树不等价。

正确的前序/后序遍历写法 #

其实和中序遍历的逻辑一样，只需要在Same函数里启动goroutine执行Walk，Walk内部的递归完全同步执行，不要给递归调用加go：

正确的前序遍历

func Walk(t *tree.Tree, ch chan int) {
    if t == nil {
        return
    }
    ch <- t.Value
    Walk(t.Left, ch)  // 同步递归，无go关键字
    Walk(t.Right, ch) // 同步递归，无go关键字
}

正确的后序遍历

func Walk(t *tree.Tree, ch chan int) {
    if t == nil {
        return
    }
    Walk(t.Left, ch)
    Walk(t.Right, ch)
    ch <- t.Value
}

这样整个遍历过程在单个goroutine里顺序执行，节点值的发送顺序严格遵循前序/后序规则，两棵相同的树会生成完全一致的序列，Same函数就能正确验证等价性了。

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