当初之所以学习Go语言,就是因为一句话:Golang天生支持并发。Java中的并发是一个比较复杂的系统,前段时间面试的时候,对于我这种CRUD Boy来说,理解并能应付并发方面的问题着实有些难度。各种概念背了一遍又一遍,current包下的东西来回练习,理解各种并发系统的设计理念,才能勉强应付一些比较水的面试。
经过几天的学习,终于跟着Go指南,学到了并发一节。在这一节中,遇到的第一个练习是判断等价二叉树。
初始代码如下
package main
import "golang.org/x/tour/tree"
// Walk 步进 tree t 将所有的值从 tree 发送到 channel ch。
func Walk(t *tree.Tree, ch chan int)
// Same 检测树 t1 和 t2 是否含有相同的值。
func Same(t1, t2 *tree.Tree) bool
func main() {
}
对于Walk函数的实现,采用递归的前序遍历,基本没什么难度。
整体思路在一开始出现了一点偏差,主要是在Same函数的实现上。刚开始想的是两个线程同时遍历两棵树,在主线程中不断的从两个channel中取出数,当遇到不同的直接返回false。写完后才意识到这样只能判断结构与数据都相同的二叉树。
经过调整,借用map以数为键,值为该数出现的次数,第一个channel负责创建map,第二个channel负责比较
这个过程中还遇到了一个坑,就是channel的关闭。刚开始将close写在了递归函数中,出现了panic。后将close该在递归函数外就可以。(很愚蠢的错误,哎)
package main
import (
"golang.org/x/tour/tree"
"fmt"
)
// Walk 步进 tree t 将所有的值从 tree 发送到 channel ch。
func Walk(t *tree.Tree, ch chan int){
ch <- t.Value
fmt.Println(t.Value)
if t.Left != nil{
Walk(t.Left,ch)
}
if t.Right != nil{
Walk(t.Right,ch)
}
}
// Same 检测树 t1 和 t2 是否含有相同的值。
func Same(t1, t2 *tree.Tree) bool{
ch1 := make(chan int,10)
ch2 := make(chan int,10)
m := make(map[int]int)
go func(){
Walk(t1,ch1)
close(ch1)
}()
go func(){
Walk(t2,ch2)
close(ch2)
}()
for{
//将ch1的数据存入map
v,f:=<- ch1
if f{
k,_:=m[v]
m[v]=k+1
}else{
break
}
}
for{
//比较ch1的数据
v,f:=<-ch2
if f {
k,_:=m[v]
if k == 0{
return false
}else{
m[v]=k-1
}
}else{
break
}
}
return true
}
func main() {
fmt.Println(Same(tree.New(2),tree.New(2)))
}
有疑问加站长微信联系(非本文作者)