Description

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 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.

Interface

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 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) {

    }
};

Solution

由题意可知，父节点的值一定小于等于两个子节点的值，因而根节点的值一定是最小值，那么可以推导出值第二小的节点在根节点的左子树中或在根节点的右子树中或不存在，同时，当一个节点的值大于根节点的值(即最小值)时，由于父节点的值一定小于等于两个子节点的值，那么由该节点衍生的子树的节点的值一定大于等于该节点的值，因此该节点衍生的子树并不需要检查。

解决的方法有多种，这里我使用了 BFS（广度优先搜索）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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:
    // unrecursion by BFS
    int findSecondMinimumValue(TreeNode* root) {
        queue<TreeNode*> que;
        que.push(root);
        int min = root->val;
        int left, right, smin = INT_MAX;
        while (!que.empty()) {
            TreeNode* temp = que.front();
            if (min < temp->val) {
                smin = (smin > temp->val ? temp->val : smin);
                que.pop();
                continue;
            }
            if (temp->left != NULL && temp->right != NULL) {
                que.push(temp->left);
                que.push(temp->right);
            }
            que.pop();
        }
        return smin == INT_MAX ? -1 : smin;
    }
};

Improvement

学习了一下 LeetCode 上讨论区的做法，将递归和分治的做法也写出来。

Recursion Method（递归方法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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:
    // recursion
    int findSecondMinimumValue(TreeNode* root) {
        if (!root) return -1;
        return findSecMin(root, root->val);
    }

    int findSecMin(TreeNode* node, int first) {
        if (!node) return -1;
        if (node->val > first) return node->val;

        int left = findSecMin(node->left, first);
        int right = findSecMin(node->right, first);

        if (left == -1 && right == -1) return -1;
        if (left != -1 && right == -1) return left;
        if (right != -1 && left == -1) return right;
    }
};

Divide and Conquer Method （分治方法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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:  
    // divide and conquer
    int findSecondMinimumValue(TreeNode* root) {
        if (!root) return -1;
        if (!root->left && !root->right) return -1;

        int left = root->left->val;
        int right = root->right->val;

        if (left == root->val)
            left = findSecondMinimumValue(root->left);
        if (right == root->val)
            right = findSecondMinimumValue(root->right);

        if (left == -1 && right == -1) return -1;
        else if (left == -1) return right;
        else if (right == -1) return left;
        else return left > right ? right : left;
    }
};