题目描述

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。

给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。

样例

输入: 
    2
   / \
  2   5
     / \
    5   7

输出: 5
解释: 最小的值是 2，第二小的值是 5。

输入: 
    2
   / \
  2   2

输出: -1
说明: 最小的值是 2，但是不存在第二小的值。

算法

(递归遍历) $O(n)$

1. 找次小值需要自顶向下遍历，找到比树根值（最小值）大的最小的数。
2. 递归遍历时，如果当前结点为空，则直接返回。
3. 如果当前结点的值与最小值不同，则更新次小值；由于每个结点的值都不会大于其子树的所有结点，所以此时可以直接返回。
4. 如果当前结点的值与最小值相同，则递归左右子树。

时间复杂度

• 每个结点最多遍历一次，故时间复杂度为 $O(n)$。

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:
    void find(TreeNode *r, int minr, int &ans) {
        if (!r)
            return;
        if (r -> val != minr) {
            if (ans == -1)
                ans = r -> val;
            else
                ans = min(ans, r -> val);
            return;
        }
        find(r -> left, minr, ans);
        find(r -> right, minr, ans);
    }
    int findSecondMinimumValue(TreeNode* root) {
        int ans = -1;
        find(root, root -> val, ans);
        return ans;
    }
};