友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-05-01 21:29:51
*/
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
public int findSecondMinimumValue(TreeNode root) {
dfs(root);
return queue.isEmpty() || queue.size() == 1 ? -1 : queue.poll();
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
if (queue.isEmpty()
|| (queue.peek() != root.val && !queue.contains(root.val))) {
queue.offer(root.val);
}
if (queue.size() > 2) {
queue.poll();
}
dfs(root.left);
dfs(root.right);
}