# 2022-06-22

## [513. Find Bottom Left Tree Value](https://leetcode.com/problems/find-bottom-left-tree-value/)

### Description

Given the `root` of a binary tree, return the leftmost value in the last row of the tree.

**Example 1:**

![](https://img.content.cc/a/2022/06/22/07-13-02-721-4ecf0611746881b7fc7955a2b15a5870-86fa20.png)

```
Input: root = [2,1,3]
Output: 1
```

**Example 2:**

![](https://img.content.cc/a/2022/06/22/07-13-14-094-5e00013b246721ea83bb5be7510ce76c-ec9d00.png)

```
Input: root = [1,2,3,4,null,5,6,null,null,7]
Output: 7
```

**Constraints:**

* The number of nodes in the tree is in the range `[1, 10^4]`.
* `-23^1 <= Node.val <= 23^1 - 1`

### Solution

#### Approach #0: BFS

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) (ans int) {
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[i]
            if i == 0 {
                ans = node.Val
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        queue = queue[size:]
    }
    return
}
```

#### Approach #1: BFS

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) (ans int) {
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        ans = node.Val
    }
    return
}
```

#### Approach #2: DFS

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) (ans int) {
    var cur int
    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, depth int) {
        if node == nil {
            return
        }
        depth++
        dfs(node.Left, depth)
        dfs(node.Right, depth)
        if depth > cur {
            cur = depth
            ans = node.Val
        }
    }
    dfs(root, 0)
    return
}
```