首页 >后端开发 >Golang >Go中如何准确判断二叉树等价?

Go中如何准确判断二叉树等价?

DDD
DDD原创
2024-12-09 16:51:11543浏览

How Can We Accurately Determine Binary Tree Equivalence in Go?

Go Tour 练习 #7 中的二叉树等价

Go 中的二叉树

Go Tour 的二叉树练习中的相同函数比较两个二叉树是否树具有相同的值。挑战在于确定何时完全遍历两棵树以声明它们相等。

解决方案

原始实现尝试使用通道来比较值。然而,它面临着确定通道何时为空的问题。

另一种方法采用高阶函数和闭包来优雅地发出树结束条件的信号。增强的 Walk 函数利用闭包来初始化 walk 函数。闭包确保通道在函数返回时关闭,防止由于递归而导致通道过早关闭。

这是更正后的 Walk 函数:

func Walk(t *tree.Tree, ch chan int) {
    defer close(ch) // Closes the channel when the function returns
    var walk func(t *tree.Tree)
    walk = func(t *tree.Tree) {
        if t == nil {
            return
        }
        walk(t.Left)
        ch <- t.Value
        walk(t.Right)
    }
    walk(t)
}

此修改后的方法可确保通道关闭仅在发送所有值后,Same 才能准确比较树的等效性。

以上是Go中如何准确判断二叉树等价?的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn