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

Question

我正在尝试用 O(1) space 解决 leetcode.com 上的 Leaf-Similar Trees 问题，而没有 concurrency/goroutines。

迭代解决方案需要堆栈来存储节点，递归解决方案需要内存来进行函数调用。

然而，在 Morris Traversal 算法的帮助下，我能够以 O(1) 内存遍历每棵树（顺便说一句，这很棘手，因为使用该算法检测叶子并非易事）。

现在我有一个问题，如何遍历两棵树并比较 1) 它们具有相同数量的叶子和 2) 相同的顺序。

显而易见的方法是将两个叶子序列存储在 arrays/slices 中，然后比较它们。但是，它会破坏 O(1) 内存。我还可以将第一棵树序列存储在一个数组中，然后从第二棵树中一个一个地生成值，将它们与数组中的值进行比较，但它仍然违反 O(1).

所以我通过使用 goroutines 发送来自两次 Morris 遍历的值来作弊，有效地创建了中间数组并实现了 O(1) space.

现在我试图通过不使用 goroutines 或任何其他并发技术来使这个解决方案更通用。一定是顺序解。

或者，我怀疑没有并发是不可能完成这个工作的，请确认是否属实。

这是我的解决方案：

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
}

Answer 1

我认为它可以在没有并发的情况下工作，并且仍然符合您的标准。它不漂亮，但它似乎工作...

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

我在 playground here 中整理了一个使用已弃用 testing.Main 的示例，以证明它对 5 个示例同样有效。

https://play.golang.org/p/hIk4zM3qpsT

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

Non-concurrent O(1) space solution for Leaf-Similar Trees Leetcode Problem

algorithm

tree

binary-tree

go