public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

class Solution {
    func findBottomLeftValue(_ root: TreeNode?) -> Int {
        guard let root = root else {
            return 0
        }
        var queue: [TreeNode] = [root]
        while !queue.isEmpty {
            let oldQueue = queue
            let count = queue.count
            var newCount = 0
            for _ in 0..<count {
                let node = queue.removeFirst()
                if let left = node.left {
                    queue.append(left)
                    newCount += 1
                }
                if let right = node.right {
                    queue.append(right)
                    newCount += 1
                }
            }
            if newCount == 0 {
                return oldQueue.first!.val
            }
        }
        return 0
    }
}
