leetCodeTreeEasy.swift

// https://leetcode.com/problems/maximum-depth-of-binary-tree/
// Recursive
// Time: O(n), Space: O(n)
func maxDepth(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }
    return 1 + max(maxDepth(root.left), maxDepth(root.right))
}

// Iterative
// Time: O(n), Space: O(n)
func maxDepth(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }

    var stack = [(TreeNode, Int)]()
    stack.append((root, 1))

    var maxDepth = 0
    while !stack.isEmpty {
        let (node, depth) = stack.popLast()!
        maxDepth = max(depth, maxDepth)
        if let left = node.left { stack.append((left, depth + 1)) }
        if let right = node.right { stack.append((right, depth + 1)) }
    }

    return maxDepth
}