题目描述

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.

解法一

思路

这题需要注意几个很关键的条件:

  • 结点只会不存在子结点或存在两个子结点;
  • 子结点的值一定不小于父结点(可能相等);
  • 两个子结点间没有大小关系。

第二小的结点实际上就是大且仅大于根结点的结点。但这里注意一个陷阱:如果根结点的左子结点比根结点大,那么左子结点不一定是第二小的结点,因为右子结点可能比左子结点小。

注意到子结点的值可能与父结点的值相等,那么第二小的结点就不一定是根结点的左子结点或右子结点了,而可能是其所有子孙结点。那么这题用递归的方法就会是一个很好的解法了。下面来描述一下递归的工作过程,每次递归都是返回以当前结点为根结点的树中仅大于当前结点的结点,那么根结点的递归返回的就是第二小的结点了:

  1. 如果当前结点不存在子结点,那么也就不存在比当前结点大的子孙结点,返回-1
  2. 如果当前结点存在子结点:

    1. 如果左子结点的值与当前结点的值不相等,那么记录左子结点的值(左子结点一定是左子树中仅大于当前结点的结点);否则左子结点的值与当前结点的值相等,则记录递归返回的左子树中仅大于左子结点的的结点(实际就是左子树中仅大于当前结点的结点)。
    2. 如果右子结点的值与当前结点的值不相等,那么记录右子结点的值(右子结点一定是右子树中仅大于当前结点的结点);否则右子结点的值与当前结点的值相等,则记录递归返回的右子树中仅大于右子结点的的结点(实际就是右子树中仅大于当前结点的结点)。
  3. 这时一定会得到记录的左子树中仅大于当前结点的结点L,以及右子树中仅大于当前结点的结点R

    1. 如果LR均为-1,则代表不存在比当前结点更大的结点,返回-1
    2. 如果LR中有且仅有其中一个为-1,则不为-1的那个就是仅大于当前结点的结点,返回这个结点。
    3. 如果LR均不为-1,则LR中较小者即为仅大于当前结点的结点,返回此结点。

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def findSecondMinimumValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root.left is None and root.right is None:
            return -1
        left = self.findSecondMinimumValue(
            root.left) if root.val == root.left.val else root.left.val
        right = self.findSecondMinimumValue(
            root.right) if root.val == root.right.val else root.right.val
        if left == -1 and right == -1:
            return -1
        if left == -1:
            return right
        if right == -1:
            return left
        return min(left, right)

Java

/**
 * 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.left == null && root.right == null) {
            return -1;
        }
        int left = root.val == root.left.val ? findSecondMinimumValue(root.left) : root.left.val;
        int right = root.val == root.right.val ? findSecondMinimumValue(root.right) : root.right.val;
        if (left == -1 && right == -1) {
            return -1;
        }
        if (left == -1) {
            return right;
        }
        if (right == -1) {
            return left;
        }
        return Math.min(left, right);
    }
}

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:
    int findSecondMinimumValue(TreeNode *root) {
        if (root->left == nullptr && root->right == nullptr) {
            return -1;
        }
        int left = root->val == root->left->val ? findSecondMinimumValue(root->left) : root->left->val;
        int right = root->val == root->right->val ? findSecondMinimumValue(root->right) : root->right->val;
        if (left == -1 && right == -1) {
            return -1;
        }
        if (left == -1) {
            return right;
        }
        if (right == -1) {
            return left;
        }
        return min(left, right);
    }
};