What is the core idea behind solving the 'Second Minimum Node In a Binary Tree' problem?

The core idea is to traverse the tree using DFS while tracking the smallest and second smallest unique values.

How can I optimize the solution for large trees in this problem?

You can optimize by using early exit during traversal once the second minimum value is found.

Does the second minimum node always exist in the tree?

No, if all nodes are identical or there is only one unique value, the second minimum will not exist, and the answer should be -1.

Can the tree contain duplicate values?

Yes, the tree can contain duplicate values, which is why you must carefully track the smallest and second smallest values separately.

How does this problem relate to binary tree traversal patterns?

This problem emphasizes DFS for tree traversal while also incorporating state tracking, which is key to identifying the second smallest value efficiently.

#671

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

二叉树中第二小的节点

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0 。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。更正式地说，即 root.val = min(root.left.val, root.right.val) 总成立。给出这样的一个二叉…

树深度优先搜索二叉树

题目描述

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 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 <= 2³¹ - 1
对于树中每个节点 root.val == min(root.left.val, root.right.val)

lightbulb

解题思路

方法一：DFS

直接 DFS 遍历二叉树，找到大于 root.val 的最小值。若不存在，则返回 -1。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是二叉树的节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if root:
                dfs(root.left)
                dfs(root.right)
                nonlocal ans, v
                if root.val > v:
                    ans = root.val if ans == -1 else min(ans, root.val)

        ans, v = -1, root.val
        dfs(root)
        return ans

speed

复杂度分析

指标	值
时间	and space complexity are dependent on the traversal method. In the worst case, the solution requires O(N) time to traverse all nodes, where N is the number of nodes in the tree. Space complexity depends on the depth of the tree, O(H) where H is the tree's height for DFS.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Does the candidate demonstrate an understanding of binary tree properties and DFS?
question_mark
How efficiently does the candidate optimize the traversal process?
question_mark
Can the candidate handle edge cases like trees without a second minimum value?

warning

常见陷阱

外企场景

error
Incorrectly assuming that there will always be a second minimum value in the tree.
error
Failure to correctly update the second minimum value during DFS traversal.
error
Not properly handling trees with repetitive values, which may lead to incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to work on a generic binary tree, where nodes can have any number of children.
arrow_right_alt
Expand the problem to return the k-th smallest value instead of just the second minimum.
arrow_right_alt
Adapt the problem to handle non-unique nodes or nodes with different values in a more complex tree structure.

help

常见问题

外企场景

继续练习

#669 修剪二叉搜索树 #662 二叉树最大宽度 #655 输出二叉树