Go Exercise: Equivalent Binary Treesへの挑戦　その２

前回の続きです。

並行処理、チャンネルは使わずに実装してみる

func walk(t *tree.Tree, n int) {
	n++
	// 左から探索
	if t.Left != nil {
		tl := t.Left
		// 孫が存在すればさらに探索
		if tl.Left != nil || tl.Right != nil {
			walk(tl, n)
		} else {
			// そうでないなら値を表示
			fmt.Println("左　深さ:", n+1, "値", tl.Value)
		}
	}
	// 左の探索が済んでいるので自分の値を表示
	fmt.Println("  深さ:", n, "値", t.Value)
	// 右を探索
	if t.Right != nil {
		tr := t.Right
		// 孫がいればさらに探索
		if tr.Left != nil || tr.Right != nil {
			walk(tr, n)
		} else {
			//　そうでないなら値を表示
			fmt.Println("右　深さ:", n+1, "値", tr.Value)
		}
	}
}
func main() {
	t1 := tree.New(1)
	t2 := tree.New(1)
	fmt.Println(t1)
	walk(t1, 0)
	fmt.Println(t2)
	walk(t2, 0)
}
実行結果
((((1 (2)) 3 (4)) 5 ((6) 7 ((8) 9))) 10)
　　深さ: 4 値 1
右　深さ: 5 値 2
　　深さ: 3 値 3
右　深さ: 4 値 4
　　深さ: 2 値 5
左　深さ: 4 値 6
　　深さ: 3 値 7
左　深さ: 5 値 8
　　深さ: 4 値 9
　　深さ: 1 値 10
((((1) 2 (3)) 4 (5 (6))) 7 ((8) 9 (10)))
左　深さ: 4 値 1
　　深さ: 3 値 2
右　深さ: 4 値 3
　　深さ: 2 値 4
　　深さ: 3 値 5
右　深さ: 4 値 6
　　深さ: 1 値 7
左　深さ: 3 値 8
　　深さ: 2 値 9
右　深さ: 3 値 10

このwalk関数のPrintlnの部分をチャンネルの送受信に置き換えれば出来そうな気はする。ページの文章に

A function to check whether two binary trees store the same sequence is quite complex in most languages. We'll use Go's concurrency and channels to write a simple solution.

とあるようにGoのゴルーチン(並行処理)を使用すれば他の言語よりシンプルにできるよ(何がシンプルかはわからない)と書いてあるので、違う気がする。ただ２つの二分木を比べるのをシンプルにできるとあるので探索自体をシンプルにできるかどうかはわからない。

普通にもっと単純なのあった

ちょっと不明な要素が多かったので調べると以下のシンプルなコードで普通に動いた。

func Walk(t *tree.Tree) {
	if t == nil {
		return
	}
	if t.Left != nil {
		Walk(t.Left)
	}
	fmt.Println(t.Value)
	if t.Right != nil {
		Walk(t.Right)
	}
}
func main() {
	Walk(tree.New(1))
}

しかしこれも他の言語で実装することが難しい訳ではない。そうなると実装が大変なのはSame関数、もしくはコンピュータ内での実際の処理がシンプルになって処理速度が早い(メモリ消費が少ないなど)というのがあげられる。とりあえずSame関数を実装してみよう。

Same関数の実装

package main
import (
	"golang.org/x/tour/tree"
	"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 == nil {
		return
	}
	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)
	b := true
	for i := 0; i < 10; i++ {
		v1 := <- ch1
		v2 := <- ch2
		if v1 != v2 {
			b = false
		}
	}
	return b
}

実行結果

func main() {
	b := Same(tree.New(1), tree.New(1))
	if b {
		fmt.Println("same")
	} else {
		fmt.Println("not same")
	}
}
// same

func main() {
	b := Same(tree.New(1), tree.New(2))
	if b {
		fmt.Println("same")
	} else {
		fmt.Println("not same")
	}
}
// not same

あれ？おっかし〜な〜？もっと大変な予定だったんだけど割とあっさり。

調べたらめっちゃ簡単なのありました

上のGithubのコードが見つけたものです。というか検索したら多分一番上に出てきます。確かにこれなら３行で行けますね。
また、二つのコードに分けることでチャンネルを閉じることができるので、任意の大きさの二分木に対して探索を行えます。今回の問題は１０に固定していたのでループを10回で回せば閉じる必要はありませんが。

感想

難しかったです。が脳汁がドバドバ出て楽しかったです。