LeetCode-2 Keys Keyboard

这道题题意理解起来会有些奇怪，翻译成可以看懂的话，就是跟节点是最小的，每个节点要么有两个子节点，要么没有，如果有的话，它等于子节点中较小的那个。现在，找出所有节点中第二小（也就是刚好比根节点大的那个）。

这样一想，是不是找根节点的子节点，如果某个子节点和根节点不一样，就是它了，如果两个子节点和根节点一样，就再去找子节点的字节点就可以了呢？非也。因为如果一个子节点和根节点相同，另一个不同的话，和根节点相同的那个子节点的子节点可能会比根节点的另一个子节点小（但是又比根节点大），所以，如果遇到子节点和根节点相同，要递归地找下去才行。

那如何确定比根节点大，却比其他节点都小呢，这就牵扯到在递归时候的选择了，首先，如果是一个底层的局部（三个节点组成的小树），就需要选择子节点中比较大的那个（因为根节点和它的父节点相等），如果是整体，就要选返回上来的值中比较小的那个。

[1,1,3,1,1,3,4,3,1,1,8]是一个典型的示例，在最下面一层的时候，需要选比较大的（3、8 和 4），而在倒数第二层的时候，left 和 right 变成了 3、8 和 4，这时候就需要在其中选更小的了。具体的算法如下所示：

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