sponsored links

golang 实现 等价查找二叉树

刚接触go语言半年,日常工作都是用小组内自研的going框架开发,对golang底层的并发机制并不是非常熟悉,近期特地研究了一下,简单实现个小算法

不同二叉树的叶节点上可以保存相同的值序列。例如,以下两个二叉树都保存了序列 `1,1,2,3,5,8,13`。

golang 实现 等价查找二叉树

在大多数语言中,检查两个二叉树是否保存了相同序列的函数都相当复杂。 我们将使用 Go 的并发和信道来编写一个简单的解法。

本例使用了 tree 包,它定义了类型:

type Tree struct {
    Left  *Tree
    Value int
    Right *Tree
}

下面是代码实现

package main

import (
	"fmt"
	"golang.org/x/tour/tree"
)
// Walk 步进 tree t 将所有的值从 tree 发送到 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 检测树 t1 和 t2 是否含有相同的值。
func Same(t1, t2 *tree.Tree) bool {
	ch1 := make(chan int, 10)
	ch2 := make(chan int, 10)
	Walk(t1, ch1)
	Walk(t2, ch2)
	for i:=0 ; i<10 ; i++ {
		v1 := <- ch1
		v2 := <- ch2
		if v1 != v2 {
			return false
		}
	}
	return true
}

func main() {
	result := Same(tree.New(10), tree.New(9))
	fmt.Println(result)
}

 

Tags: