LeetCode 0513.找树左下角的值

找树左下角的值

LeetCode513. 找树左下角的值

题目描述

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

假设二叉树中至少有一个节点。

思路

本地要找出树的最后一行的最左边的值。用层序遍历是非常简单的，只需要记录最后一行第一个节点的数值就可以了，反而用递归的话会比较难一点

代码

Go

 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
31


func findBottomLeftValue(root *TreeNode) int {
    //初始化列表(双向链表)
    queue := list.New()
    //定义变量res记录层级
    var res int
    //根节点入队
    queue.PushBack(root)
    //遍历列表中所有节点(包括新加入的下一层节点)
    for queue.Len() > 0 {
        //保存列表长度到length
        length := queue.Len()
        //遍历一层的所有节点(遇到孩子节点则入队)
        for i := 0; i < length; i++ {
            //队列的头节点出队
            node := queue.Remove(queue.Front()).(*TreeNode)
            //更新res 记录该层的最左节点值到res
            if i == 0 {
                res = node.Val
            }
            //若遍历到的节点有左孩子,则入队
            if node.Left != nil {
                queue.PushBack(node.Left) //入队
            }
            //若遍历到的节点有右孩子,则入队
            if node.Right != nil {
                queue.PushBack(node.Right) //入队
            }
        }
    }
    return res
}

Link

GitHub