如何解决此二叉树反序列化问题？

Question

这个serialize()函数的bug在哪里

我在 Swift 中写了一个函数 deserialize() 来从一个可选的整数数组构造一个二叉树。我通过将输出与使用具有相同数组的手动方法构建的树的输出进行比较来测试此功能。他们看起来一样，这很好！

但是，当我运行另一个函数 isSameTree() 用于比较 2 棵树时（我确信这个函数工作正常），反序列化（）的输出和手动方法的输出，我有不同的结果！

我假设 deserialize() 不正确，但我找不到错误！

// 辅助代码

public class BinaryNode {
     public var value: Int
     public var left: BinaryNode?
     public var right: BinaryNode?
     public init(_ value: Int) {
         self.value = value
         self.left = nil
         self.right = nil
     }
 }

extension BinaryNode {
    public var description: String {
        return diagram(for: self)
    }
    private func diagram(for node: BinaryNode?,
                         _ top: String = "",
                         _ root: String = "",
                         _ bottom: String = "") -> String {
        guard let node = node else {
            return root + "nil\n"
        }
        if node.left == nil && node.right == nil {
            return root + "\(node.value)\n"
        }
        return diagram(for: node.right,
                       top + " ", top + "┌──", top + "│ ")
            + root + "\(node.value)\n"
            + diagram(for: node.left,
                      bottom + "│ ", bottom + "└──", bottom + " ")
    }
}

public func deserialize(_ array: inout [Int?]) -> BinaryNode? {
    guard !array.isEmpty, let value = array.removeFirst() else {
        return nil
    }
    let node = BinaryNode(value)
    node.left = deserialize(&array)
    node.right = deserialize(&array)
    return node
}

func isSameTree(_ p: BinaryNode?, _ q: BinaryNode?) -> Bool {
        guard let p = p else {
            return q == nil
        }
        guard let q = q else {
            return p == nil
        }

        if p.value != q.value {
            return false
        }

        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    }


// Using deserialize to construct trees
var a1: [Int?] = [1,nil,2,3]
var a2: [Int?] = [1,nil,2,nil,3]
if let tree = deserialize(&a1) {
    print(tree.description)
}

if let tree = deserialize(&a2) {
    print(tree.description)
}

// Using manual to construct trees
let a3: BinaryNode = {
    let one = BinaryNode(1)
    let two = BinaryNode(2)
    let three = BinaryNode(3)
    one.right = two
    two.left = three
    return one
}()
print(a3.description)
let a4: BinaryNode = {
    let one = BinaryNode(1)
    let two = BinaryNode(2)
    let three = BinaryNode(3)
    one.right = two
    two.right = three
    return one
}()
print(a4.description)

// The print statements above show similar trees are constructed
// However, below results are not same

isSameTree(deserialize(&a1), deserialize(&a2)) // true <- this is wrong
isSameTree(a3, a4) // false <--- this is correct

Answer 1

您似乎忘记了您的 deserialize(_:) 对其参数具有破坏性...请记住您为什么需要 &。

//Re-load a1 & a2...
a1 = [1,nil,2,3]
a2 = [1,nil,2,nil,3]
print(isSameTree(deserialize(&a1), deserialize(&a2))) //-> false
print(isSameTree(a3, a4)) //-> false

如何解决此二叉树反序列化问题？

How to fix this Binary Tree Deserialize problem?

algorithm

serialization

binary-tree

deserialization

swift