173. Binary Search Tree Iterator

class BSTIterator {
    var stack = [TreeNode]()
    init(_ root: TreeNode?) {
        guard let root = root else{ return }
        pushLeft(root)
    }

    private func pushLeft(_ node : TreeNode){
        var runner = node
        stack.append(node)
        while runner.left != nil{
            stack.append(runner.left!)
            runner = runner.left!
        }
    }

    /** @return the next smallest number */
    //每次next 的时候 pushLeft
    func next() -> Int {
        if stack.count > 0 {
            let cur = stack.removeLast()
            if let right = cur.right{
                pushLeft(right)
            }
            return cur.val
        }
        return 0
    }

    /** @return whether we have a next smallest number */
    //只要stack不空都说明还有东西
    func hasNext() -> Bool {
        return stack.count > 0
    }
}