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   7Output: 5Explanation: The smallest value is 2, the second smallest value is 5.

Example 2:

Input:     2   / \  2   2Output: -1Explanation: The smallest value is 2, but there isn't any second smallest value. 不是二叉搜索树！当心，必须要过完所有的结点才知道答案！

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def findSecondMinimumValue(self, root):        """        :type root: TreeNode        :rtype: int        """        inf = float('inf')        min1, min2 = inf, inf               # min1 < min2                def dfs(node):            nonlocal min1, min2            if not node: return                        dfs(node.left)              if node.val != min1 and node.val != min2:                if node.val < min1:                    min2 = min1                    min1 = node.val                elif node.val < min2:                    min2 = node.val            dfs(node.right)                assert root        dfs(root)        return min2 if min2 != inf else -1

 貌似我理解题目错了。

Based on the special property of the tree, we can guarantee that the root node is the smallest node in the tree. We just have to recursively traverse the tree and find a node that is bigger than the root node but smaller than any existing node we have come across.

- Yangshun

class Solution(object):    def findSecondMinimumValue(self, root):        res = [float('inf')]        def traverse(node):            if not node:                return            if root.val < node.val < res[0]:                res[0] = node.val            traverse(node.left)            traverse(node.right)        traverse(root)        return -1 if res[0] == float('inf') else res[0]

 

学到闭包写法！如果不使用nonlocal的话！

 

类似我这样直接暴力，只是没有利用root信息：

def findSecondMinimumValue(self, root):    self.ans = float('inf')    min1 = root.val    def dfs(node):        if node:            if min1 < node.val < self.ans:                self.ans = node.val            elif node.val == min1:                dfs(node.left)                dfs(node.right)    dfs(root)    return self.ans if self.ans < float('inf') else -1

 

 

还有就是常规的思路：

public int findSecondMinimumValue(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 value same as root value, need to find the next candidate    if (root.left.val == root.val) {        left = findSecondMinimumValue(root.left);    }    if (root.right.val == root.val) {        right = findSecondMinimumValue(root.right);    }        if (left != -1 && right != -1) {        return Math.min(left, right);    } else if (left != -1) {        return left;    } else {        return right;    }}

 

public int findSecondMinimumValue(TreeNode root) {    int rootVal = root.val;    int secondSmall =Integer.MAX_VALUE;    boolean diffFound = false;    Queue
     
       Q= new LinkedList
      
       ();    Q.add(root);    while(!Q.isEmpty())    {        TreeNode curr=Q.poll();        if(curr.val!=rootVal && curr.val < secondSmall)        {            secondSmall=curr.val;            diffFound=true;        }        if(curr.left!=null)        {            Q.add(curr.left);            Q.add(curr.right);        }    }    return (secondSmall == Integer.MAX_VALUE && !diffFound) ? -1 : secondSmall;}