swift - Swift 中的 DFS 没有终止

问题描述

我的 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 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
            }
        }
    }
}

标签： swiftbinary-tree

swift - Swift 中的 DFS 没有终止

问题描述

解决方案

推荐阅读