j

jaryue

V1

2023/05/02阅读:9主题:默认主题

leetcode 671. 二叉树中第二小的节点

leetcode 671. 二叉树中第二小的节点.


题目描述

  1. 二叉树中第二小的节点

给定一个非空特殊的二叉树,每个节点都是正数,并且每个节点的子节点数量只能为 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

先序遍历\

  1. 我们使用两个变量来储存最小的数与第二小的数,那么第二小的数有两种变换情况:
  2. 最小的数出现更小的数,就是当遍历的节点值小于最小的数时,最小的数赋值为该节点值,第二小的数赋值为刚刚最小的数
  3. 节点数值大于最小的数,小于第二小的数,,那么第二小的数就赋值为节点数值
  4. 遍历整个树找到第二小的数
  • 细节注意,我们定义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