巡回练习：等效二叉树

Question

I am trying to solve equivalent binary trees exercise on go tour. Here is what I did;

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)))
}

However, I couldn't find out how to signal if any no more elements left in trees. I can't use close(ch) on Walk() because it makes the channel close before all values are sent (because of recursion.) Can anyone lend me a hand here?

Answer 1

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 walkRecurseis more or less your current Walk function, but recursing on walkRecurse. (or you rewrite Walk to be iterative - which, granted, is more hazzle) 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'l have to implement the countTreeNodes()function, which should count the number of nodes in a *Tree