Итеративный обход порядка в Swift неверный ответ

Question

Здесь есть реализация псевдокода: https://algorithms.tutorialhorizon.com/inorder-traversal-non-recursive-approach/ итеративного порядка, который я реализовал в Swift.

Псевдокод:

Создание стека.Вставьте корень в стек и установите root = root.left продолжить, пока он не достигнет значения NULL.Если root равен нулю, а стек пуст, то вернемся, все готовоВ противном случае вставьте верхний узел из стека и установите его как root = popped_Node.распечатайте корень и идите направо, root = root.right.Переходите к шагу 2. Конец, если

Однако я повторяю последний элемент.

Мой адрес:

func inOrderDFSIterative() -> [Int] {
    var s = [self]
    var curr : Node? = self
    var outputArr: [Int] = []

    while !s.isEmpty    {
        // reach the leftmost node of the current Node
        while curr != nil {
            s.append(curr!)
            curr = curr!.left
        }
        curr = s.popLast()!
        outputArr.append(curr!.data)
        curr = curr?.right
    }
    return outputArr
}

Который является частью моего двоичного файлакласс дерева

class Node: Hashable {
    static func == (lhs: Node, rhs: Node) -> Bool {
        return lhs.data == rhs.data
    }
    var hashValue: Int {
        return data
    }

    var data : Int
    var left : Node? = nil
    var right : Node? = nil

    init(_ data : Int) {
        self.data = data
    }

    func insert (_ data : Int) {
        if data < self.data {
            if let lft = left {
                lft.insert(data)
            } else {
                let newNode = Node(data)
                left = newNode
            }
        } else {
            if let rgt = right {
                rgt.insert(data)
            } else {
                let newNode = Node(data)
                right = newNode
            }
        }
    }
}

Я установил дерево

let regularTree = Node(20)
regularTree.insert(8)
regularTree.insert(4)
regularTree.insert(12)
regularTree.insert(10)
regularTree.insert(14)
regularTree.insert(22)

, и функция normalTree.inOrderDFSIterative () возвращает вместо [4, 8, 10, 12, 14, 20, 22, 20] вместо [4, 8, 10, 12, 14, 20, 22], что, очевидно, неверно.В чем здесь проблема?

Answer 1

Убедитесь, что s не пусто перед добавлением curr!.data к outputArr:

curr = s.popLast()!
if !s.isEmpty {
    outputArr.append(curr!.data)
    curr = curr?.right
}

---

Вообще говоря, избегайте принудительного развертывания и используйте больше Swifty такие способы, как необязательное связывание или конструкция guard:

while !s.isEmpty    {
    // reach the leftmost node of the current Node
    while let current = curr {
        s.append(current)
        curr = current.left
    }
    curr = s.popLast()
    if !s.isEmpty, let current = curr {
        outputArr.append(current.data)
        curr = current.right
    }
}