使用Goroutines在Go语言中比较两棵树等价的通道实现难题

你当前的代码存在几个关键问题，导致无法正确实现两棵树的等价性比较：

1. 同步调用Walk导致阻塞：直接调用Walk(t1, t1Ch)时，因为通道是无缓冲的，发送元素ch <- t.Value会一直阻塞，直到有接收方读取，而此时没有goroutine在接收，程序会卡死。
2. 仅比较单个元素：匿名goroutine只读取了两个通道的第一个元素就返回结果，没有遍历所有元素，无法判断整棵树是否等价。
3. 通道未关闭：Walk函数遍历结束后没有关闭通道，接收方会一直等待新元素，导致死锁。

修正后的代码实现 #

package main

import (
	"fmt"
)

// Tree 定义二叉树结构
type Tree struct {
	Left  *Tree
	Value int
	Right *Tree
}

func Walk(t *Tree, ch chan int) {
	defer close(ch) // 遍历完成后关闭通道
	var walk func(*Tree)
	walk = func(n *Tree) {
		if n == nil {
			return
		}
		walk(n.Left)
		ch <- n.Value
		walk(n.Right)
	}
	walk(t)
}

func Same(t1, t2 *Tree) bool {
	ch1 := make(chan int)
	ch2 := make(chan int)

	// 启动goroutine执行Walk，避免阻塞
	go Walk(t1, ch1)
	go Walk(t2, ch2)

	for {
		v1, ok1 := <-ch1
		v2, ok2 := <-ch2

		// 两个通道都关闭且最后一个元素相等，说明等价
		if !ok1 && !ok2 {
			return true
		}
		// 一个关闭另一个未关闭，或者元素不相等，说明不等价
		if ok1 != ok2 || v1 != v2 {
			return false
		}
	}
}

func main() {
	// 测试用例：两棵等价和一棵不等价的树
	root := &Tree{Value: 2, Left: &Tree{Value: 1}, Right: &Tree{Value: 3}}
	root1 := &Tree{Value: 2, Left: &Tree{Value: 1}, Right: &Tree{Value: 3}}
	root2 := &Tree{Value: 2, Left: &Tree{Value: 1}, Right: &Tree{Value: 4}}

	fmt.Println(Same(root, root1)) // 输出 true
	fmt.Println(Same(root, root2)) // 输出 false
}

关键修正点说明 #

• 用goroutine启动Walk：避免同步调用导致的阻塞，让遍历在后台异步执行。
• Walk函数末尾关闭通道：使用defer close(ch)确保遍历完成后关闭通道，让接收方明确知道没有更多元素需要读取。
• 完整遍历比较逻辑：在Same函数中循环读取两个通道的元素，同时判断通道的状态：
  • 若两个通道都关闭且所有元素对应相等，返回true
  • 若一个通道关闭另一个未关闭（树的节点数量不同），或对应位置元素不相等，返回false

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