513.find-bottom-left-tree-value.md

513. Find Bottom Left Tree Value

BFS

fun findBottomLeftValue(root: TreeNode?): Int {
    if (root == null) return 0
    val queue = ArrayDeque<TreeNode>()
    queue.addLast(root)
    var leftmost = 0
    while (queue.isNotEmpty()) {
        val size = queue.size
        for (i in 0 until size) {
            val node = queue.removeFirst()
            if (i == 0) leftmost = node.`val`

            if (node.left != null) queue.addLast(node.left)
            if (node.right != null) queue.addLast(node.right)
        }
    }
    return leftmost
}

DFS

private var currentLevel = -1
private var leftmost = 0

fun findBottomLeftValue(root: TreeNode?): Int {
    dfs(root, 0)
    return leftmost
}

private fun dfs(root: TreeNode?, level: Int) {
    if (root == null) return
    // Update answer only when reaching the first node of new level
    if (currentLevel < level) {
        leftmost = root.`val`
        currentLevel = level
    }
    dfs(root.left, level + 1)
    dfs(root.right, level + 1)
}

• Time Complexity: O(n).
• Space Complexity: O(h).