Swift 中的 DFS 未终止

Question

我的 BFS 实现工作正常：

func bfsReturnVals() -> [Int] {
    // bfs uses a queue.
    var queue = [Node]()
    var queueVals = [Int]()
    queue.append(self)
    while let head = queue.first {
        if let lft = head.left {
            queue.append(lft)
        }
        if let rgt = head.right {
            queue.append(rgt)
        }
        queueVals.append(queue[0].data)
        queue.removeFirst()
    }

    return queueVals
}

但我通常递归地编写 DFS。现在我类似的 DFS 实现不会终止

func dfsReturnVals() -> [Int] {
    var stack = [Node]()
    var queueVals = [Int]()
    stack.append(self)
    while let tail = stack.last {
        if let lft = tail.left {
            stack.append(lft)
        }
        if let rgt = tail.right {
            stack.append(rgt)
        }
        queueVals.append(stack[stack.count - 1].data)
        stack.removeLast()
    }
    return queueVals
}

我不知道为什么。 removeLast() 不应该像 removeFirst() 一样工作吗？

我的节点class如下：

class Node : CustomStringConvertible {
    var description : String {return "\(self.data)" }
    var data : Int
    var left: Node?
    var right: Node?

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

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

Answer 1

当您从堆栈中移除最后一个项目时，您将移除刚刚推送的项目。在您的 bfs 实现中，先删除将获取预期的父节点，而不管您是在循环结束时执行它，因为您将子节点添加到队列的末尾。在推送新节点之前，您应该将操作从堆栈中删除展开的节点。

Swift 中的 DFS 未终止

DFS in Swift not terminating

binary-tree

swift