Go并发 - 二叉查找树是否相同

使用 Go 并发比较两棵二叉查找树。

在做A Tour of Go的时候遇到的并发的问题，具体问题看这里 (不过就是需要翻墙)。题目所生成的二叉树总是等长的，这就很好解决，这位CSDN博主就给出了很好的解决方案。但我想的是：如果树不等长呢? 我这里给出了一个解决方案

package main

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

// Walk 步进 tree t 将所有的值从 tree 发送到 channel ch。
func Walk(t *tree.Tree, ch chan int, depth int) {
    // dfs, in-order
    if t == nil {
        return
    }
    Walk(t.Right, ch, depth+1)
    ch <- t.Value
    Walk(t.Left, ch, depth+1)
    
    if depth == 0 {
        close(ch)
    }
}

// Same 检测树 t1 和 t2 是否含有相同的值。
func Same(t1, t2 *tree.Tree) bool {
    c1 := make(chan int)
    c2 := make(chan int)
    go Walk(t1, c1, 0)
    go Walk(t2, c2, 0)
    for{
        x,o1 := <-c1
        y,o2 := <-c2
        if !o1 || !o2 {
            if o1 != o2 {
                //树结点数目不一
                return false;
            } else{
                break;
            }
        }
        if x != y {
            return false
        }
    }
    return true
}

func main() {
    t := tree.New(1)
    m := tree.New(1)
    fmt.Println(Same(t,m))
}

---

本文最初发布于简书。

Donate