[Day36]-[二叉树]- 找树左下角的值
作者:方勇(gopher)
- 2022 年 5 月 06 日
本文字数:429 字
阅读完需:约 1 分钟
513. 找树左下角的值
给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
复制代码
示例 1:
![](https://static001.geekbang.org/infoq/1d/1d5cd593b49f808a739cd63ae7a076eb.jpeg?x-oss-process=image/resize,p_80/auto-orient,1)
输入: root = [2,1,3]
输出: 1
复制代码
示例 2:
![](https://static001.geekbang.org/infoq/7d/7d0b745b9e64f971b52d37ed606ae4d4.jpeg?x-oss-process=image/resize,p_80/auto-orient,1)
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
复制代码
题解:深度优先,定义一个深度最大值,每次第一次访问某一层元素时就max
赋值当前深度。
func TestFindBottomLeftValue(t *testing.T) {
var root = &TreeNode{Val: 1}
var maxDept = math.MinInt
var res int
var findBottomLeftValue func(root *TreeNode) int
var dfs func(root, prev *TreeNode, depth int)
dfs = func(root, prev *TreeNode, depth int) {
if root == nil {
return
}
if maxDept < depth{
maxDept = depth
res = root.Val
}
dfs(root.Left, root, depth+1)
dfs(root.Right, root, depth+1)
}
findBottomLeftValue = func(root *TreeNode) int {
res = root.Val
dfs(root, root, 0)
return res
}
t.Log(findBottomLeftValue(root))
}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 6
![用户头像](http://static001.geekbang.org/account/avatar/00/13/b1/81/13f23d1e.jpg?x-oss-process=image/resize,w_200,h_200)
方勇(gopher)
关注
Dead or Alive. 生存战斗是知识的源泉! 2018.11.08 加入
我是一名SRE哨兵,目前是好大夫基础架构部高级工程师。专注于 SRE,微服务、中间件的稳定性和可用性建设,整体负责好大夫服务治理云平台的设计和搭建!
评论