本篇文章向大家介绍《LeetCode 叶相似树问题的非并发 O(1) 空间解决方案》,主要包括,具有一定的参考价值,需要的朋友可以参考一下。
问题内容
我正在尝试用 o(1) 空间没有并发/goroutines解决 leetcode.com 上的叶相似树问题。
迭代解决方案需要堆栈来存储节点,递归解决方案需要内存用于函数调用。
但是,在 morris 遍历算法的帮助下,我能够使用 o(1) 内存遍历每棵树(顺便说一句,这很棘手,因为使用此算法检测叶子并非易事)。
现在我有一个问题,如何遍历两棵树并比较 1) 它们具有相同数量的叶子,2) 顺序相同。
最明显的方法是将两个叶子序列存储在数组/切片中,然后比较它们。然而,它会破坏 o(1) 内存。我还可以将第一个树序列存储在数组中,并逐一生成第二个树的值,将它们与数组中的值进行比较,但它仍然违反 o(1)。
因此,我通过使用 Goroutine 发送来自 morris 遍历的值来进行作弊,从而有效地不创建中间数组并实现 o(1) 空间。
现在我试图通过不使用 goroutine 或任何其他并发技术来使这个解决方案更加通用。它必须是一个顺序解决方案。
或者,我怀疑如果没有并发就不可能完成这项工作,请确认是否属实。
这是我的解决方案:
func leafSimilar(root1 *Treenode, root2 *TreeNode) bool {
getLeafs := func(node *TreeNode, ch chan int) {
var pre *TreeNode // predecessor of the current node
curr := node
for curr != nil {
if curr.Left == nil {
if curr.Right == nil {
ch <- curr.Val
}
curr = curr.Right
continue
}
// curr.Right != nil
pre = curr.Left
for pre.Right != nil && pre.Right != curr {
pre = pre.Right
}
if pre.Right == nil {
pre.Right = curr
curr = curr.Left
continue
}
// pre.Right == curr
pre.Right = nil
if pre.Left == nil { // tricky! not using curr, but pre
ch <- pre.Val
}
curr = curr.Right
}
close(ch)
}
ch1 := make(chan int)
ch2 := make(chan int)
go getLeafs(root1, ch1)
go getLeafs(root2, ch2)
similar := true
for {
val1, ok1 := <-ch1
val2, ok2 := <-ch2
if val1 != val2 || ok1 != ok2 {
similar = false
}
if ok1 == false && ok2 == false {
break
}
}
return similar
}
解决方案
我认为它可以在没有并发的情况下工作,并且仍然符合您的标准。它不漂亮,但似乎有用……
func leafsimilarnoconcurrency(root1 *treenode, root2 *treenode) bool {
if root1 == root2 {
return true
}
getleafs := func(curr *treenode, pre *treenode) (int, *treenode, *treenode, bool) {
for curr != nil {
if curr.left == nil {
if curr.right == nil {
//ch <- curr.val
return curr.val, curr.right, pre, true
}
curr = curr.right
continue
}
// curr.right != nil
pre = curr.left
for pre.right != nil && pre.right != curr {
pre = pre.right
}
if pre.right == nil {
pre.right = curr
curr = curr.left
continue
}
// pre.right == curr
pre.right = nil
if pre.left == nil { // tricky! not using curr, but pre
// ch <- pre.val
return pre.val, curr.right, pre, true
}
curr = curr.right
}
return 0, nil, nil, false
}
var val1, val2 int
var pre1, pre2 *treenode
var ok1, ok2 bool
curr1, curr2 := root1, root2
similar := true
for {
val1, curr1, pre1, ok1 = getleafs(curr1, pre1)
val2, curr2, pre2, ok2 = getleafs(curr2, pre2)
if val1 != val2 || ok1 != ok2 {
similar = false
}
if ok1 == false && ok2 == false {
break
}
}
return similar
}
执行一点基准测试,它甚至可能更快(至少对于 example1 测试用例)…
goos: windows
goarch: amd64
BenchmarkLeafSimilar-4 244850 5509 ns/op 192 B/op 2 allocs/op
BenchmarkLeafSimilarNoConcurrency-4 13185218 92.9 ns/op 0 B/op 0 allocs/op
PASS
ok _/d_/Build/morristree 2.893s
我整理了一个使用已弃用的测试的示例。此处演示中的主要部分,以证明它对于 5 个示例的工作原理相同。
https://play.golang.org/p/hIk4zM3qpsT
本篇关于《Leetcode 叶相似树问题的非并发 O(1) 空间解决方案》的介绍就到此结束啦,但是学无止境,想要了解学习更多关于Golang的相关知识,请关注编程网公众号!