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.
参加contest遇到的题，不过我没做出来。我一直困于如何去利用题目中树的特殊性：有两个孩子或者没有；根节点是两个子节点中较小的那个。
但实际上我提醒过自己很多次，题目拿来先想最最straightforward的方法，也就是逻辑最简单的暴力解法。这道题我曾经很多次想到干脆用tree traversal来写，然后记录所有节点，最后在节点中找第二小的就好了。但是一直很纠结，觉得自己没利用的题目，怕继续想。再一个也是我不知道如何记录traverse到的所有节点。所以，也给以后提个醒。尽量先能写出来，不管多笨，先写出来要紧。这道题其他的写法我暂时不是很理解，先掌握最简单的吧，一步步来。
我是在网上看到其他语言写的这种用Set的方法，以及在stackoverflow找到的如何拿到kth element in a hashSet的方法。然后用preOrder traversal来遍历树，把所有遍历过的节点都记录到HashSet里面，最后再取第二小的就可以了。
/**
* 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 == null){
return -1;
}
Set<Integer> set = new HashSet<>();
preOrder(root, set);
if (set.size() < 2){
return -1;
}
int index = 0;
for (Integer num : set){
if (index == 1){
return num;
}
index++;
}
return -1;
}
private void preOrder(TreeNode head, Set<Integer> set){
if (head == null){
return;
}
set.add(head.val);
preOrder(head.left, set);
preOrder(head.right, set);
}
}
