426. Convert Binary Search Tree to Sorted Doubly Linked List

func TreeNodeToDoubleList(_ root: Node?) -> Node?{
    guard let root = root else { return nil}
    var stack = [Node]()
    pushLeft(root, &stack)

    var pre : Node?
    var head: Node?
    while stack.count > 0{
        let cur = stack.removelAST()
        if let right = cur.right {
            pushLeft(right, &stack)
        }
        if pre == nil {
            head = cur
        }else {
            pre.right = cur
            cur.left = pre
        }
        pre = cur
    }
    //最后这个是为了把整体的头尾链成环
    if let head = head {
        head.right = pre
        pre!.left = head
    }
    return head
}

func pushLeft(_ root: Node, _ stack : inout [Node]) {
    stack.append(root)
    var runner = root
    while runner.left != nil{
        stack.append(runner.left!)
        runner = runner.left
    }
}