-
Notifications
You must be signed in to change notification settings - Fork 0
/
second-minimum-node-in-a-binary-tree.js
69 lines (61 loc) · 1.51 KB
/
second-minimum-node-in-a-binary-tree.js
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* 671. 二叉树中第二小的节点
* @param {TreeNode} root
* @return {number}
*/
var findSecondMinimumValue = function(root) {
// 哈希集合去重
const set = new Set();
const dfs = (root) => {
if (root) {
set.add(root.val);
dfs(root.left);
dfs(root.right);
}
}
dfs(root);
if (set.size < 2) return -1;
// 两个变量 & 一次遍历 找到次小值
let first = Number.MAX_VALUE; // 第一小值
let second = Number.MAX_VALUE; // 第二小值
// 1,3,-1,2
set.forEach(val => {
if (val <= first) {
second = first;
first = val;
} else if (val <= second) {
second = val;
}
})
return second;
};
var findSecondMinimumValue2 = function(root) {
// 递归
// root.val = min(root.left.val, root.right.val)
// 由于这个条件总是成立, 因此: 根节点必然是全局最小值
let result = -1;
const dfs = (root, curr) => {
if (root) {
if (root.val !== curr) {
if (result === -1) { // 第一次赋值
result = root.val;
} else {
result = Math.min(result, root.val);
}
return;
}
dfs(root.left, curr);
dfs(root.right, curr);
}
}
dfs(root, root.val);
return result;
}