关于golang:GO-语言之旅-练习等价二叉查找树

题目地址 https://tour.go-zh.org/concur…
前提：对两棵二叉树进行中序遍历，若是失去的数值序列雷同，则将其视为等价二叉树。
要求：应用 goroutine 协程

思维：其实和不应用协程的思路差不多，别离中序遍历两棵树，失去数值序列，比拟两个序列是否相等。
若是应用协程，则能够很不便地并发遍历两棵树，再利用信道传输每个节点的数值，边遍历边比拟。因为 Go 协程可利用多 CPU 外围，若是电脑有两个以上的 CPU 外围，则理论的运行工夫会大大放慢。
相似的，在其余编程语言里，能够应用多线程，而后通过队列传送信息给主线程。边遍历边比拟。

树的数据结构。文档和源代码地址：https://pkg.go.dev/golang.org…

// A Tree is a binary tree with integer values.
type Tree struct {
    Left  *Tree
    Value int
    Right *Tree
}

题目的模板揭示咱们，通过 Same 函数检测两棵树是否雷同，通过 Walk 函数遍历树。
思维就是，在 Same 函数中别离创立两个信道 ch1，ch2，启动两个协程运行Walk 函数，两个 Walk 函数别离遍历两棵树，别离通过两个信道将遍历的数值传给 Same 函数，Same会同时比对两个 Walk 传输过去的数值，若是直到两个 Walk 遍历完树（也就是两个 Walk 都敞开了信道），Same的数值比对都没有出错，则可视为两棵树等价。

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

理论代码

package main

import "fmt"
import "tree"

// Walk 步进 tree t 将所有的值从 tree 发送到 channel ch。func Walk(t *tree.Tree, ch chan int) {
    if t == nil {return}
    stack := make([]*tree.Tree, 0)
    for len(stack) > 0 || t != nil {
        for t != nil {stack = append(stack, t)
            t = t.Left
        }
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        ch <- node.Value
        t = node.Right
    }
    close(ch)
}

// Same 检测树 t1 和 t2 是否含有雷同的值。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 {
        // 两个信道都在开启状态
            if v1 != v2 {return false}
        } else if ok1 || ok2 {
        // 一个信道已敞开，阐明两棵树节点数不同
            return false
        } else {
        // 两个信道同时敞开，阐明两棵树节点数雷同
            break
        }
    }
    return true
}

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

在 Walk 中，能够创立一个切片 ”stack“ 来模仿栈实现中序遍历。压入栈是 stack = append(stack, t), 弹出栈是node := stack[len(stack)-1]，stack = stack[:len(stack)-1]。每遍历一个节点，就将数值传入信道ch。遍历实现，敞开信道close(ch)。
在Same中，创立两个协程同时遍历两棵树，两个信道别离接管两个 Walk 传来的数值。两棵树等价的必要条件就是，树的节点数雷同，若是有一棵树提前遍实现，则代表这棵树节点数少一些，这两棵树必然不等价。只有两棵树都同时遍历实现，且每次比对数值不出错，才可视为两棵树等价。