## 题目描述

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.

Example 1:

``````Input:
2
/ \
2   5
/ \
5   7

Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.``````

Example 2:

``````Input:
2
/ \
2   2

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

## 解法一

### 思路

• 结点只会不存在子结点或存在两个子结点；
• 子结点的值一定不小于父结点（可能相等）；
• 两个子结点间没有大小关系。

1. 如果当前结点不存在子结点，那么也就不存在比当前结点大的子孙结点，返回`-1`
2. 如果当前结点存在子结点：

1. 如果左子结点的值与当前结点的值不相等，那么记录左子结点的值（左子结点一定是左子树中仅大于当前结点的结点）；否则左子结点的值与当前结点的值相等，则记录递归返回的左子树中仅大于左子结点的的结点（实际就是左子树中仅大于当前结点的结点）。
2. 如果右子结点的值与当前结点的值不相等，那么记录右子结点的值（右子结点一定是右子树中仅大于当前结点的结点）；否则右子结点的值与当前结点的值相等，则记录递归返回的右子树中仅大于右子结点的的结点（实际就是右子树中仅大于当前结点的结点）。
3. 这时一定会得到记录的左子树中仅大于当前结点的结点`L`，以及右子树中仅大于当前结点的结点`R`

1. 如果`L``R`均为`-1`，则代表不存在比当前结点更大的结点，返回`-1`
2. 如果`L``R`中有且仅有其中一个为`-1`，则不为`-1`的那个就是仅大于当前结点的结点，返回这个结点。
3. 如果`L``R`均不为`-1`，则`L``R`中较小者即为仅大于当前结点的结点，返回此结点。

### Python

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def findSecondMinimumValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root.left is None and root.right is None:
return -1
left = self.findSecondMinimumValue(
root.left) if root.val == root.left.val else root.left.val
right = self.findSecondMinimumValue(
root.right) if root.val == root.right.val else root.right.val
if left == -1 and right == -1:
return -1
if left == -1:
return right
if right == -1:
return left
return min(left, right)``````

### Java

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int findSecondMinimumValue(TreeNode root) {
if (root.left == null && root.right == null) {
return -1;
}
int left = root.val == root.left.val ? findSecondMinimumValue(root.left) : root.left.val;
int right = root.val == root.right.val ? findSecondMinimumValue(root.right) : root.right.val;
if (left == -1 && right == -1) {
return -1;
}
if (left == -1) {
return right;
}
if (right == -1) {
return left;
}
return Math.min(left, right);
}
}``````

### C++

``````/**
* 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:
int findSecondMinimumValue(TreeNode *root) {
if (root->left == nullptr && root->right == nullptr) {
return -1;
}
int left = root->val == root->left->val ? findSecondMinimumValue(root->left) : root->left->val;
int right = root->val == root->right->val ? findSecondMinimumValue(root->right) : root->right->val;
if (left == -1 && right == -1) {
return -1;
}
if (left == -1) {
return right;
}
if (right == -1) {
return left;
}
return min(left, right);
}
};``````