找树左下角的值
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