j
jaryue
V1
2023/05/02阅读:9主题:默认主题
leetcode 671. 二叉树中第二小的节点
leetcode 671. 二叉树中第二小的节点.
题目描述
-
二叉树中第二小的节点
给定一个非空特殊的二叉树,每个节点都是正数,并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话,那么该节点的值等于两个子节点中较小的一个。
更正式地说,即 root.val = min(root.left.val, root.right.val) 总成立。
给出这样的一个二叉树,你需要输出所有节点中的 第二小的值 。
如果第二小的值不存在的话,输出 -1 。
示例 1:
输入:root = [2,2,5,null,null,5,7] 输出:5 解释:最小的值是 2 ,第二小的值是 5 。 示例 2:
输入:root = [2,2,2] 输出:-1 解释:最小的值是 2, 但是不存在第二小的值。
提示:
树中节点数目在范围 [1, 25] 内 1 <= Node.val <= 231 - 1 对于树中每个节点 root.val == min(root.left.val, root.right.val)
解题思路
法1
先序遍历\
-
我们使用两个变量来储存最小的数与第二小的数,那么第二小的数有两种变换情况: -
最小的数出现更小的数,就是当遍历的节点值小于最小的数时,最小的数赋值为该节点值,第二小的数赋值为刚刚最小的数 -
节点数值大于最小的数,小于第二小的数,,那么第二小的数就赋值为节点数值 -
遍历整个树找到第二小的数
-
细节注意,我们定义32位最大值问第二大的初始值,当数值第二大的值为32位最大值时就无法判断是否有第二大值(没有返回1),所以要增加一个判断条件 -
时间复杂度(O(n)) -
空间复杂度(O(1))
执行结果
法1
func findSecondMinimumValue(root *TreeNode) int {
if root == nil {
return -1
}
minVal := root.Val
secondMinVal := math.MaxInt32
secondpd:=false
var traverse func(node *TreeNode)
traverse = func(node *TreeNode) {
if node == nil {
return
}
if node.Val > minVal && node.Val <= secondMinVal {
secondpd= true
secondMinVal = node.Val
} else if node.Val == minVal {
traverse(node.Left)
traverse(node.Right)
}
}
traverse(root)
if !secondpd {
return -1
}
return secondMinVal
}
执行结果: 通过 显示详情 查看示例代码 添加备注
执行用时: 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗: 1.8 MB , 在所有 Go 提交中击败了 73.75% 的用户 通过测试用例: 39 / 39 炫耀一下:
法2
法3
作者介绍
j
jaryue
V1