513. 找树左下角的值

题目描述

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

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示:

二叉树的节点个数的范围是 [1,10⁴]
-2³¹ <= Node.val <= 2³¹ - 1

解法一：DFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) int {
    res, maxDepth := root, 0
    var dfs func(root *TreeNode, depth int)
    dfs = func(root *TreeNode, depth int) {
        if root != nil {
            depth += 1
            if root.Left == nil && root.Right == nil {
                // 只有当 depth > maxDepth 时才更新 res
                if depth > maxDepth {
                    maxDepth = depth
                    res = root
                }
                return
            }
            // 为了确保是最左边节点的值，需要先遍历左子树！
            dfs(root.Left, depth)
            dfs(root.Right, depth)
        }
    }
    dfs(root, 0)
    return res.Val
}

解法二：BFS

官方题解如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


func findBottomLeftValue(root *TreeNode) (ans int) {
    q := []*TreeNode{root}
    for len(q) > 0 {
        node := q[0]
        q = q[1:]
        if node.Right != nil {
            q = append(q, node.Right)
        }
        if node.Left != nil {
            q = append(q, node.Left)
        }
        ans = node.Val
    }
    return
}