一、问题描述

给定一个二叉树的根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

示例

输入:

    1
   / \
  2   3
 /   / \
4   5   6
   /
  7

输出: 7

解释:

在这个二叉树中，最左下角的值是7，因为它是最后一行中最左边的值。

二、方案一：广度优先搜索（BFS）

1、思路

使用广度优先搜索（BFS）遍历树，每一层从左到右遍历，这样最后一个遍历到的节点就是最左下角的值。

2、代码实现

func findBottomLeftValue(root *TreeNode) int {
    queue := []*TreeNode{root}
    var result int
    for len(queue) > 0 {
        levelSize := len(queue)
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            if i == 0 {
                result = node.Val // 每层的第一个节点
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return result
}

3、复杂度分析

• 时间复杂度：O(n)，其中n是树中节点的数量。每个节点都会被访问一次。
• 空间复杂度：O(m)，其中m是树的最大宽度。在最坏的情况下，树是一个完全二叉树，队列中最多会有m个节点。

三、方案二：深度优先搜索（DFS）

1、思路

使用深度优先搜索（DFS）遍历树，记录当前的最大深度和对应的最左边的值。在遍历过程中，如果当前节点的深度大于已记录的最大深度，则更新最大深度和对应的值。

2、代码实现

var maxDepth int
var leftMostValue int
func findBottomLeftValue(root *TreeNode) int {
    maxDepth = -1
    leftMostValue = 0
    dfs(root, 0)
    return leftMostValue
}
func dfs(node *TreeNode, depth int) {
    if node == nil {
        return
    }
    if depth > maxDepth {
        maxDepth = depth
        leftMostValue = node.Val
    }
    dfs(node.Left, depth+1)
    dfs(node.Right, depth+1)
}

3、复杂度分析

• 时间复杂度：O(n)，其中n是树中节点的数量。每个节点都会被访问一次。
• 空间复杂度：O(h)，其中h是树的高度。在最坏的情况下，树是一个倾斜的树，递归栈的深度为h。

四、总结

两种方案都可以解决问题，BFS更直观，而 DFS 则需要额外的变量来记录最大深度和对应的最左边的值。在大多数情况下，BFS是更常用的方法，因为它更易于理解和实现。