LeetCode671 Second Minimum Node In a Binary Tree

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.

If no such second minimum value exists, output -1 instead.

样例

1
2
3
4
5
6
7
8
9
Input: 
2
/ \
2 5
/ \
5 7

Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.
1
2
3
4
5
6
7
Input: 
2
/ \
2 2

Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.

思路

给一颗非空的二叉树,结点权值为非负数。这棵二叉树有一个特殊的性质:每个结点要么没有儿子结点,要么一定有两个儿子结点,并且两个儿子结点的权值都大等于该节点的权值。现在,要求出这颗二叉树中第二小的权值是多少,若不存在则输出“-1”。

根据其性质,显然最小值为根结点的权值。那么,第二小的权值就应该等于除了根结点权值外的那个最小值。

所以,从根结点开始,若当前节点权值等于根结点权值,那么继续$dfs$下去。直到不相等的时候,说明该权值有可能是候选答案,与当前最优答案取个$min$即可,并且此时也不用继续搜下去,根据其性质可知后代结点不可能是答案。

对于不存在的情况,一开始可以设置答案$ans$为无穷大(由于valint类型,因此可以设置为INT_MAX)。若$dfs$结束之后,$ans$没有改变的话,说明不存在答案,此时输出“-1”即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void dfs(TreeNode* root, int minVal, int& ans) {
if (root == nullptr) return ;
if (root->val == minVal) {
dfs(root->left, minVal, ans);
dfs(root->right, minVal, ans);
} else ans = min(ans, root->val);
}
int findSecondMinimumValue(TreeNode* root) {
int ans = INT_MAX;
dfs(root, root->val, ans);
return ans == INT_MAX ? -1 : ans;
}
};
分享到 评论