Как исправить эту проблему? - PullRequest
Новая
       17

Как исправить эту проблему?

0 голосов
/ 14 мая 2019

Где ошибка в этой функции serialize ()

Я написал функцию deserialize () в Swift для построения двоичного дерева из массива необязательного Integer. Я протестировал эту функцию, сравнив выходные данные с выходными данными дерева, построенного ручным методом с тем же массивом. Они выглядят одинаково, что хорошо!

Однако, когда я запускаю другую функцию isSameTree (), которая используется для сравнения 2 деревьев (я уверен, что эта функция работает правильно), при выводе deserialize () и выводе ручного метода, я получаю разные результаты!

Я полагаю, что 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

1 Ответ

1 голос
/ 15 мая 2019

Кажется, вы забыли, что ваш 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
...