Exercise: Equivalent Binary Trees (二叉树对比)

A Tour of Go

Exercise: Equivalent Binary Trees

https://tour.golang.org/concurrency/7

检查两棵二叉树是否包含相同的数值,这题难度稍大,有几个难点。

答案如下:

其中,函数 walk 用递归方法遍历二叉树

在 walk 的外面再包裹一层 Walk 是为了 close(ch)

而 close(ch) 是为了判断这棵树是否已经遍历完毕,以便结束循环。

注意,上面这个答案有个小问题,在官方答案里有这样的备注:

NOTE: The implementation leaks goroutines when trees are different.

其原因是这样的,首先,两棵树所包含的数值全部被读取并分别发送到 ch1 和 ch2 中,当两棵树包含的数值不相同时,上面程序中的 for 循环被中止并返回 false, 但是,此时被发送到 ch1 或/及 ch2 的数值还没有全部被接收,因此,它们会一直处于等待被接收的状态(在教程里有这样一句话:By default, sends and receives block until the other side is ready),以这种状态留存在内存中(占用内存),相当于内存泄漏。(当然,当这个程序关闭时,即可释放这部分内存,因此对于非长期运行的小程序来说问题不大。)

解决办法见官方答案:

https://github.com/golang/tour/blob/master/solutions/binarytrees_quit.go

参考相关讨论:

https://groups.google.com/forum/#!topic/golang-nuts/gva8SmZGmek

原文地址:https://www.cnblogs.com/ahui2017/p/6383616.html