巡回练习：等效二叉树

小编典典

巡回练习：等效二叉树

我正在尝试解决等效的二叉树演习。这是我所做的；

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

但是，我无法找出如何发信号通知树中是否还剩下任何元素。我无法使用close(ch)on，Walk()因为它会使通道在所有值发送之前关闭（因为递归。）有人可以在这里帮我吗？

阅读 390

2020-07-02

共1个答案

小编典典

如果Walk函数本身不递归，则可以使用close（）。即步行将做：

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

其中walkRecurse或多或少是您当前的Walk功能，但是在walkRecurse上递归。（或者您将Walk重写为迭代式的-
理所当然，这更加令人生厌）使用这种方法，您的Same（）函数必须了解Channels已关闭，这是通过表单的channel接收完成的

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

当ok1和ok2彼此不同时，或者当两者都不同时，采取适当的措施false

另一种方法（但可能不是本练习的精神）是计算树中的节点数：

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
}

您必须实现countTreeNodes（）函数，该函数应该计算* Tree中的节点数

2020-07-02