Easy
之前的方法是直接traverse数，然后放到set里面，遍历到第二小的返回.
这里运用到了hashSet里面如果放的是integer会自动排序这个特点，注意这个特点对string类型并不适用. 但这个方法没有用到题目给的树的特点，就不再叙述了.
这题的思路，YouTube上有位叫Huahua的讲得不错的。根据这个树的特点，我们知道第一小的Node肯定是root, 然后开始搜索第二小的点. 如果说root为空或者说root没有孩子，那么以这个节点为根结点的树并没有第二小的node,返回-1. 如果有左右孩子，我们再DFS在左右子树里面找. 注意我们搜索之前先判断左右子节点val跟根结点是否相等，如果大于根结点，那我们直接返回改子节点的val.因为我们知道如果接下去继续找只会找到比这个子节点更大的，对我们来说是没有意义的搜索. 如果该节点值等于根结点值，那么我们就要继续搜索下去，寻找以该节点为root的第二小的节点，有可能遇到其他candidates.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
//树只会考你recursion或者divide and conquer
class Solution {
public int findSecondMinimumValue(TreeNode root) {
return dfsHelper(root);
}
private int dfsHelper(TreeNode root){
if (root == null){
return -1;
}
if (root.left == null && root.right == null){
return -1;
}
int left = root.left.val;
int right = root.right.val;
if (left == root.val){
left = dfsHelper(root.left);
}
if (right == root.val){
right = dfsHelper(root.right);
}
if (left != -1 && right != -1){
return Math.min(left, right);
} else if (left != -1){
return left;
} else {
return right;
}
}
}
