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

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

题目描述

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

先序遍历\

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