去旅游练习 # 7: 二叉树等价

我试图解决 等效二叉树等效二叉树练习在去旅游。这里是我所做的;

package main


import "tour/tree"
import "fmt"


// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
if t.Left != nil {
Walk(t.Left, ch)
}
ch <- t.Value
if t.Right != nil {
Walk(t.Right, ch)
}


}


// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1 := make(chan int)
ch2 := make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)
for k := range ch1 {
select {
case g := <-ch2:
if k != g {
return false
}
default:
break
}
}
return true
}


func main() {
fmt.Println(Same(tree.New(1), tree.New(1)))
fmt.Println(Same(tree.New(1), tree.New(2)))
}

然而，我无法找到如何信号，如果没有更多的元素留在树上。我不能在 Walk()上使用 close(ch)，因为它会在发送所有值之前关闭通道(因为是递归的)有人能帮我一把吗？

32810 次浏览
小开
最佳答案

You could use close() if your Walk function doesn't recurse on itself. i.e. Walk would just do:

func Walk(t *tree.Tree, ch chan int) {
walkRecurse(t, ch)
close(ch)
}

Where walkRecurse is more or less your current Walk function, but recursing on walkRecurse. (or you rewrite Walk to be iterative - which, granted, is more hassle) With this approach, your Same() function have to learn that the channels was closed, which is done with the channel receive of the form

k, ok1 := <-ch
g, ok2 := <-ch

And take proper action when ok1 and ok2 are different, or when they're both false

Another way, but probably not in the spirit of the exercise, is to count the number of nodes in the tree:

func Same(t1, t2 *tree.Tree) bool {
countT1 := countTreeNodes(t1)
countT2 := countTreeNodes(t2)
if countT1 != countT2 {
return false
}
ch1 := make(chan int)
ch2 := make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)
for i := 0; i < countT1; i++ {
if <-ch1 != <-ch2 {
return false
}
}
return true
}

You'll have to implement the countTreeNodes() function, which should count the number of nodes in a *Tree

小开

An elegant solution using closure was presented in the golang-nuts group,

func Walk(t *tree.Tree, ch chan int) {
defer close(ch) // <- closes the channel when this function returns
var walk func(t *tree.Tree)
walk = func(t *tree.Tree) {
if t == nil {
return
}
walk(t.Left)
ch <- t.Value
walk(t.Right)
}
walk(t)
}
小开

This is my solution. It properly checks for differences in the length of the two sequences. 

package main


import "code.google.com/p/go-tour/tree"
import "fmt"


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


func Same(t1, t2 *tree.Tree) bool {
chana := make (chan int)
chanb := make (chan int)


go Walk(t1, chana)
go Walk(t2, chanb)


for {
n1, ok1 := <-chana
n2, ok2 := <-chanb
if n1 != n2 || ok1 != ok2 {
return false
}
if (!ok1) {
break
}
}
return true;
}
小开

You got it almost right, there's no need to use the select statement because you will go through the default case too often, here's my solution that works without needing to count the number of nodes in the tress: 

func Same(t1, t2 *tree.Tree) bool {
ch1, ch2 := make(chan int), make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)
for i := range ch1 {
j, more := <-ch2
if more {
if i != j { return false }
} else { return false }
}


return true
}
小开

Here's the full solution using ideas here and from the Google Group thread

package main


import "fmt"
import "code.google.com/p/go-tour/tree"


// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
var walker func(t *tree.Tree)
walker = func (t *tree.Tree) {
if (t == nil) {
return
}
walker(t.Left)
ch <- t.Value
walker(t.Right)
}
walker(t)
close(ch)
}


// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1, ch2 := make(chan int), make(chan int)


go Walk(t1, ch1)
go Walk(t2, ch2)


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


if v1 != v2 || ok1 != ok2 {
return false
}


if !ok1 {
break
}
}


return true
}


func main() {
fmt.Println("1 and 1 same: ", Same(tree.New(1), tree.New(1)))
fmt.Println("1 and 2 same: ", Same(tree.New(1), tree.New(2)))


}
小开

You should avoid to let opened channels unattended or a thread can be waiting forever and never ending.

package main


import "code.google.com/p/go-tour/tree"
import "fmt"


func WalkRecurse(t *tree.Tree, ch chan int) {
if t == nil {
return
}


WalkRecurse(t.Left, ch)
ch <- t.Value
WalkRecurse(t.Right, ch)
}


// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
WalkRecurse(t, ch)
close(ch)
}


// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
var ch1, ch2 chan int = make(chan int), make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)


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


if ok1 != ok2 {
ret = false
}
if ok1 && (v1 != v2) {
ret = false
}
if !ok1 && !ok2 {
break
}
}


return ret
}


func main() {
ch := make(chan int)
go Walk(tree.New(1), ch)
for v := range ch {
fmt.Print(v, " ")
}
fmt.Println()


fmt.Println(Same(tree.New(1), tree.New(1)))
fmt.Println(Same(tree.New(1), tree.New(2)))
}
小开

My version

package main




import (
"fmt"
"golang.org/x/tour/tree"
)


// Walk walks the tree t sending all values
// from the tree to the channel ch.
func WalkRec(t *tree.Tree, ch chan int) {
if t == nil {
return
}
WalkRec(t.Left, ch)
ch <- t.Value
WalkRec(t.Right, ch)
}


func Walk(t *tree.Tree, ch chan int) {
WalkRec(t, ch)
close(ch)
}


// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1 := make(chan int)
ch2 := make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)


for {
x, okx := <-ch1
y, oky := <-ch2
switch {
case okx != oky:
return false
case x != y:
return false
case okx == oky && okx == false:
return true
}


}


}


func main() {
ch := make(chan int)
go Walk(tree.New(1), ch)
fmt.Println(Same(tree.New(1), tree.New(1)))
fmt.Println(Same(tree.New(2), tree.New(1)))
fmt.Println(Same(tree.New(1), tree.New(2)))
}
小开

I wrote 2 versions that always read both channels to the end:

package main


import (
"fmt"
"golang.org/x/tour/tree"
)


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


func Same(t1, t2 *tree.Tree, sameChan func(ch1, ch2 chan int) bool) bool {
ch1, ch2 := make(chan int), make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)


return sameChan(ch1, ch2)
}


func sameChan1(ch1, ch2 chan int) bool {
areSame := true
for {
v1, ok1 := <-ch1
v2, ok2 := <-ch2


if !ok1 && !ok2 {
return areSame
}


if !ok1 || !ok2 || v1 != v2 {
areSame = false
}
}
}


func sameChan2(ch1, ch2 chan int) bool {
areSame := true
for v1 := range ch1 {
v2, ok2 := <-ch2


if !ok2 || v1 != v2 {
areSame = false
}
}
for _ = range ch2 {
areSame = false
}
return areSame
}


func main() {
fmt.Println(Same(tree.New(1), tree.New(1), sameChan1))
fmt.Println(Same(tree.New(2), tree.New(1), sameChan1))
fmt.Println(Same(tree.New(1), tree.New(2), sameChan1))


fmt.Println(Same(tree.New(1), tree.New(1), sameChan2))
fmt.Println(Same(tree.New(2), tree.New(1), sameChan2))
fmt.Println(Same(tree.New(1), tree.New(2), sameChan2))
}
小开

That's how I did it using Inorder Traversal

package main


import (
"fmt"
"golang.org/x/tour/tree"
)


// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
if t != nil {
Walk(t.Left, ch)
ch <- t.Value
Walk(t.Right, ch)
}
}


// Same determines whether the trees
// t1 and t2 contain the same values.


func Same(t1, t2 *tree.Tree) bool {
c1, c2 := make(chan int), make(chan int)
go Walk(t1, c1)
go Walk(t2, c2)
if <-c1 == <-c2 {
return true
} else {
return false
}
}


func main() {
t1 := tree.New(1)
t2 := tree.New(8)
fmt.Println("the two trees are same?", Same(t1, t2))
}
小开

because the question just said the tree just 10 nodes，then following is my answer after read other answers：

func Walk(t *tree.Tree, ch chan int) {
defer close(ch)


var walker func(t *tree.Tree)
walker = func(t *tree.Tree) {
if t == nil {
return
}


walker(t.Left)
ch <- t.Value
walker(t.Right)
}
walker(t)
}


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


for range make([]struct{}, 10) {
if <-ch1 != <-ch2 {
return false
}
}
return true
}
小开

Here's a solution that doesn't depend on differing tree lengths, neither does it depend on traversal order:

package main


import (
"fmt"
"golang.org/x/tour/tree"
)


// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
var walk func(*tree.Tree)
walk = func(tr *tree.Tree) {
if tr == nil {
return
}


walk(tr.Left)
ch <- tr.Value
walk(tr.Right)
}


walk(t)
close(ch)
}


func merge(ch chan int, m map[int]int) {
for i := range ch {
count, ok := m[i]
if ok {
m[i] = count + 1
} else {
m[i] = 1
}
}
}


// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1 := make(chan int, 100)
ch2 := make(chan int, 100)
m := make(map[int]int)


go Walk(t1, ch1)
go Walk(t2, ch2)


merge(ch1, m)
merge(ch2, m)


for _, count := range m {
if count != 2 {
return false
}
}


return true
}
小开

This is how I did it, the difference is that you can wrap Walk into anonymous function and defer close(ch) inside it. Thus you have not to define other named recursive function

package main


import (
"golang.org/x/tour/tree"
"fmt"
)
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
if t == nil {
return
}
Walk(t.Left, ch)
ch <- t.Value
Walk(t.Right, ch)
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1, ch2 := make(chan int), make(chan int)
go func() {
defer close(ch1)
Walk(t1, ch1)
}()
go func() {
defer close(ch2)
Walk(t2, ch2)
}()
for {
v1, ok1 := <- ch1
v2, ok2 := <- ch2
if ok1 != ok2 || v1 != v2 {
return false
}
if !ok1 && !ok2 {
break
}
}
return true
}


func main() {
ch := make(chan int)
go func () {
defer close(ch)
Walk(tree.New(3), ch)
}()
for i := range ch {
fmt.Println(i)
}


fmt.Println(Same(tree.New(1), tree.New(1)))
fmt.Println(Same(tree.New(1), tree.New(2)))
fmt.Println(Same(tree.New(10), tree.New(10)))
}
小开

For whoever interested, if you wonder how to solve this without creating a separate recursive function, here is an answer using a stack:

func Walk(t *tree.Tree, ch chan int) {
defer close(ch)
visitStack := []*tree.Tree{t}
visited := make(map[*tree.Tree]bool, 1)
for len(visitStack) > 0 {
var n *tree.Tree
n, visitStack = visitStack[len(visitStack)-1], visitStack[:len(visitStack)-1]
if visited[n] {
ch <- n.Value
continue
}
if n.Right != nil {
visitStack = append(visitStack, n.Right)
}
visitStack = append(visitStack, n)
if n.Left != nil {
visitStack = append(visitStack, n.Left)
}
visited[n] = true
}
}
小开

A clear answer:

package main


import "golang.org/x/tour/tree"
import "fmt"


// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
if t == nil {
return
}
Walk(t.Left, ch)
ch <- t.Value
Walk(t.Right, ch)
}


func WalkATree(t *tree.Tree, ch chan int) {
Walk(t, ch)
close(ch)
}


// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1 := make(chan int)
ch2 := make(chan int)
go WalkATree(t1, ch1)
go WalkATree(t2, ch2)
var v1, v2 int
var ok1, ok2 bool
for {
v1, ok1 = <- ch1
v2, ok2 = <- ch2
if !ok1 && !ok2 {
return true
}
if !ok1 && ok2 || ok1 && !ok2 {
return false
}
if v1 != v2 {
return false
}
}
}


func main() {
fmt.Println(Same(tree.New(1), tree.New(1)))
}
小开

Tried to solve this problem using map structure.

func Same(t1, t2 *tree.Tree) bool {
countMap := make(map[int]int)
ch := make(chan int)
go Walk(t1, ch)
for v := range ch {
countMap[v]++
}
ch = make(chan int)
go Walk(t2, ch)
for v := range ch {
countMap[v]--
if countMap[v] < 0 {
return false
}
}
return true
}
小开

While my first intuition was to also wrap the recursive walk and closing the channels, I felt it was not in the spirit of the exercise.

The exercise text contains the following information:

The function tree.New(k) constructs a randomly-structured (but always sorted) binary tree holding the values k, 2k, 3k, ..., 10k.

Which clearly states that the resulting trees have exactly 10 nodes.

Therefore, in the spirit and simplicity of this exercise, I went with the following solution:

package main


import (
"fmt"
"golang.org/x/tour/tree"
)


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


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


defer close(ch1)
defer close(ch2)


go Walk(t1, ch1)
go Walk(t2, ch2)


for i := 0; i < 10; i++ {
if <-ch1 != <-ch2 {
return false
}
}


return true
}


func main() {
fmt.Println(Same(tree.New(1), tree.New(2)))
}

If the goal would be to run on arbitrarily sized trees, then reacting to closed channels is the better solution, but I felt this was a simple exercise with intentionally put constraints to make it easier for the new Gopher.

小开

All of previous answers do not solve the task about Same function. The question is:

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same2(t1, t2 *tree.Tree) bool

It shouldn't consider structure of tree. That's why following tests fail, gives us false in both lines:

fmt.Println("Should return true:", Same(tree.New(1), tree.New(1)))
fmt.Println("Should return false:", Same(tree.New(1), tree.New(2)))

Remember?

The function tree.New(k) constructs a randomly-structured (but always sorted) binary tree holding the values k, 2k, 3k, ..., 10k.

You need just check that both trees have the same values. And task description clearly notice that:

Same(tree.New(1), tree.New(1)) should return true, and Same(tree.New(1), tree.New(2)) should return false.

So to solve the task you need buffer all results from one tree and check does the values from second tree are in the first one.

Here is my solution, it's not ideal one :) :

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1, ch2 := make(chan int), make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)


var tv1 = []int{}


for v := range ch1 {
tv1 = append(tv1, v)
}


inArray := func(arr []int, value int) bool {
for a := range arr {
if arr[a] == value {
return true
}
}
return false
}


for v2 := range ch2 {
if !inArray(tv1, v2) {
return false
}
}


return true
}
小开

Here's my solution, without the defer magic. I thought this would be a bit easier to read, so it would worth sharing :)

Bonus: This version actually solves the problem in the tour's exercise and gives proper results.

package main


import (
"golang.org/x/tour/tree"
"fmt"
)


// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
walkRecursive(t, ch)
close(ch)
}


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


// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
var br bool
ch1, ch2 := make(chan int), make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)


for i:= range ch1 {
if i == <-ch2 {
br = true
} else {
br = false
break
}
}
return br
}


func main() {
ch := make(chan int)
go Walk(tree.New(1), ch)


for i := range ch {
fmt.Println(i)
}


fmt.Println(Same(tree.New(1), tree.New(2)))
fmt.Println(Same(tree.New(1), tree.New(1)))
fmt.Println(Same(tree.New(2), tree.New(1)))
}

So the output is as follows:

1
2
3
4
5
6
7
8
9
10
false
true
false
小开 
package main


import (
"fmt"
"golang.org/x/tour/tree"
)


// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
walkRecursive(t, ch)
close(ch)
}


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


// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1 := make(chan int)
ch2 := make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)


for {
v1, ok1 := <-ch1
v2, ok2 := <-ch2
if ok1 != ok2 {
return false
}
if !ok1 {
return true
}
if v1 != v2 {
return false
}
}
}


func main() {
fmt.Println(Same(tree.New(1), tree.New(2)))
}
小开 
package main


import (
"fmt"
"golang.org/x/tour/tree"
)


// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
if t != nil {
Walk(t.Left, ch)
ch <- t.Value
Walk(t.Right, ch)
}
}


// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1, ch2 := make(chan int), make(chan int)
go func() { Walk(t1, ch1); close(ch1) }()
go func() { Walk(t2, ch2); close(ch2) }()
for v1 := range ch1 {
if v1 != <-ch2 {
return false
}
}
return true
}


func main() {
fmt.Println(Same(tree.New(1), tree.New(1)))
fmt.Println(Same(tree.New(2), tree.New(1)))
}
小开

Haven't seen it so far in this thread. I used the nil channel technique presented in just for func

The issue with closing the channels was solved by kicking them off in an goroutine iife.

I think I could check more performant for equality though. 

package main


import (
"fmt"
"reflect"
"sort"


"golang.org/x/tour/tree"
)


// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
ch <- t.Value
if t.Right != nil {
Walk(t.Right, ch)
}
if t.Left != nil {
Walk(t.Left, ch)
}


}


// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {


c1 := make(chan int)
s1 := []int{}


go func() {
Walk(t1, c1)
close(c1)
}()


c2 := make(chan int)
s2 := []int{}


go func() {
Walk(t2, c2)
close(c2)
}()


for c1 != nil || c2 != nil {
select {
case v, ok := <-c1:
if !ok {
c1 = nil
sort.Ints(s1)
continue
}
s1 = append(s1, v)
case v, ok := <-c2:
if !ok {
c2 = nil
sort.Ints(s2)
continue
}
s2 = append(s2, v)
}
}
return reflect.DeepEqual(s1, s2)
}


func main() {
fmt.Println(Same(tree.New(1), tree.New(1)))
}
小开

This is my solution.

package main


import (
"golang.org/x/tour/tree"
"fmt"
)


// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
if t == nil {
return
}
    

Walk(t.Left, ch)
ch <- t.Value
Walk(t.Right, ch)
}


// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1,ch2 := make(chan int),make(chan int)
    

go func() {
Walk(t1, ch1)
close(ch1)
}()
    

go func() {
Walk(t2, ch2)
close(ch2)
}()
    

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

if ok1 == false && ok2 == false {
return true
}
        

if v1 != v2 {
return false
}
}


return false
}


func main() {
fmt.Println(Same(tree.New(1), tree.New(1)))
fmt.Println(Same(tree.New(1), tree.New(2)))
}
小开

If one is using recursive calls with one's Walk logic and one wishes to signal channel-consumers that there are no more items, it seems that one can put the majority of one's Walk logic into a second function, invoke that second function, wait for it to complete, then close the channel.

In the example below, the second ("inner Walk") function is a "closure" directly inside the Walk function, but it needn't be.

package main


import "golang.org/x/tour/tree"
import "fmt"


// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
defer close(ch)
var iw func(*tree.Tree)
iw = func(it *tree.Tree) {
if it == nil {
return
}
iw(it.Left)
ch <- it.Value
iw(it.Right)
}
iw(t)
}


// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1 := make(chan int)
ch2 := make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)
for {
v1, more1 := <- ch1
v2, more2 := <- ch2
if (!more1 && !more2) {
return true
}
if more1 != more2 || v1 != v2 {
return false
}
}
}


func main() {
fmt.Println(Same(tree.New(1), tree.New(1)))
fmt.Println(Same(tree.New(1), tree.New(2)))
}
小开

Here's a non-recursive solution (i.e. won't have stack space issues on large inputs) that also does not require a separate visited map - it just uses a single Stack data structure. The trick to avoiding a visited map is to remove the visited entries from the stack and instead create new tree.Tree instances for the visited entries, with the Left side removed so it doesn't revisit the left side.

package main


import "fmt"
import "golang.org/x/tour/tree"


func Pop(stack []*tree.Tree) (*tree.Tree, []*tree.Tree) {
last := len(stack) - 1
node := stack[last]
stack[last] = nil
return node, stack[:last]
}


// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
defer close(ch)
stack := []*tree.Tree{t}
var node *tree.Tree
for len(stack) > 0 {
node, stack = Pop(stack)
if node.Left != nil {
stack = append(stack, &tree.Tree{nil, node.Value, node.Right}, node.Left)
continue
}


ch <- node.Value


if node.Right != nil {
stack = append(stack, node.Right)
}
}
}


// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1, ch2 := make(chan int), make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)
for {
v1, ok1 := <-ch1
v2, ok2 := <-ch2
if v1 != v2 {
return false
}
if !ok1 || !ok2 {
return ok1 == ok2
}
}
}


func PrintTree(t *tree.Tree) {
ch := make(chan int)
go Walk(t, ch)
for i := range ch {
fmt.Printf("%d ", i)
}
fmt.Println()
}


func main() {
PrintTree(tree.New(1))
PrintTree(&tree.Tree{Value: 1, Right: &tree.Tree{Value: 2}})


fmt.Println("1 and 2 same (false): ", Same(tree.New(1), tree.New(2)))
fmt.Println("1 and 1 same (true): ", Same(tree.New(1), tree.New(1)))
fmt.Println("empty same (true): ", Same(&tree.Tree{}, &tree.Tree{}))
fmt.Println("diff length same (false): ", Same(&tree.Tree{Value: 1}, &tree.Tree{Value: 2, Left: &tree.Tree{Value: 2}}))
}

The output is:

1 2 3 4 5 6 7 8 9 10
1 2
1 and 2 same (false):  false
1 and 1 same (true):  true
empty same (true):  true
diff length same (false):  false
小开

How about just change count of incoming arguments by a little?

package main


import (
"fmt"
"golang.org/x/tour/tree"
)


// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int, recursion bool) {
if t != nil {
ch <- t.Value
Walk(t.Left, ch, true)
Walk(t.Right, ch, true)
}
    

if !recursion {
close(ch)
}
}


// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
t1_map := map[int]int{}
t2_map := map[int]int{}
t1_ch := make(chan int)
t2_ch := make(chan int)
    

go Walk(t1, t1_ch, false)
go Walk(t2, t2_ch, false)
    

for value := range t1_ch {
t1_map[value]++
}
    

for value := range t2_ch {
t2_map[value]++
}
    

if len(t1_map) != len(t2_map) {
return false
}
    

for t1_key, t1_value := range t1_map {
t2_value, t2_exists := t2_map[t1_key]
        

if (!t2_exists) || (t1_value != t2_value) {
return false
}
}
    

return true
}


func main() {
t1 := tree.New(1)
t2 := tree.New(2)
t3 := tree.New(1)
    

fmt.Println(Same(t1, t2))
fmt.Println(Same(t1, t3))
fmt.Println(Same(t3, t2))
}
小开

In the author's case, they should just change the Same function to avoid an infinite loop:

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


go Walk(t1, ch1)
go Walk(t2, ch2)


if <-ch1 != <-ch2 {
return false
}


return true
}
小开

This can be solved using an iterative approach (which will save on memory). Using an iterative approach based on this example:

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
stack := make([]*tree.Tree, 0)
for {
if t != nil {
stack = append(stack, t)
t = t.Left
} else if(len(stack) > 0) {
lastIndex := len(stack) - 1
t = stack[lastIndex]
stack = stack[:lastIndex]
            

ch <- t.Value
            

t = t.Right
} else {
close(ch)
return
}
}
}
小开

Use goroutine with an anonymous function

go func() {
.... // logic
close(ch)// last close channel or defer close channel
// do not use close() outside of goroutine
}()

Here's code which can read easy

Walk func

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

Same func

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


go func() {
Walk(t1, ch1)
close(ch1)
}()
}()




go func() {
Walk(t2, ch2)
close(ch2)
}()
}()


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

if !ok1 && !ok2 {
// both closed at the same time (and all values until now were equal)
return true
}
    

if !ok1 || !ok2 || v1 != v2 {
return false
}
}
return true
}

main func

func main() {
c := make(chan int)
t1 := tree.New(1)
go func() {
Walk(t1, c)
close(c)
}()


for i := range c {
fmt.Print(i) // 12345678910
}


fmt.Println("")
result1 := Same(tree.New(1), tree.New(1))
fmt.Println(result1) // true
result2 := Same(tree.New(1), tree.New(2))
fmt.Println(result2) // false
}
小开

Adding my solution for others to reference. Not adding a lot of explanations as it is pretty similar to several others well described here. Hope it helps though. In any case, being able to compare our different approaches to these exercises is just great!

Also, you can try it code in Go playground

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


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


go Walk(t1, ch1)
go Walk(t2, ch2)


for i := range ch1 {
if i != <-ch2 {
return false
}
}
return true
}


func main() {
fmt.Printf("Positive result. Expecting true: %v\n", Same(tree.New(1), tree.New(1)))
fmt.Printf("Negative result. Expecting false: %v\n", Same(tree.New(1), tree.New(2)))
}

提交答案