513. 找树左下角的值.md

513. 找树左下角的值

题目传送门

点击这里

解题思路

根据题干的意思，就是寻找深度最深的层的最左边节点，所以这又是二叉树使用dfs或者bfs的遍历深度的问题，只不过要找最左边的节点，先处理左侧，再处理右侧即可。而bfs则要后处理左侧，目的是为了更新。

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) int {
    // 找深度最深的层的最左边节点
    // dfs
    h := 0
    var res int
    var dfs func(node *TreeNode, d int)
    dfs = func(node *TreeNode, d int) {
        if node == nil {
            return
        }
        d ++
        // 优先向左遍历 
        dfs(node.Left, d)
        dfs(node.Right, d)
        if d > h {
            h = d
            res = node.Val
        }
    }
    dfs(root, 0)
    return res
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) int {
    // 找深度最深的层的最左边节点
    // bfs
    var res 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)
        }
        res = node.Val
    }
    return res
}