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

[toc]
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

本文由mdnice多平台发布