Leetcode 叶相似树问题的非并发 O(1) 空间解决方案

本篇文章向大家介绍《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的相关知识，请关注编程网公众号！