> For the complete documentation index, see [llms.txt](https://shuati.gitbook.io/crack-lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shuati.gitbook.io/crack-lintcode/linkedin/second-minimum-node-in-a-binary-tree.md).

# Second Minimum Node In a Binary Tree

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:**<br>

```
Input: 
    2
   / \
  2   5
     / \
    5   7

Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.
```

**Example 2:**<br>

```
Input: 
    2
   / \
  2   2

Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.
```

&#x20;java 用递归写，传int 值得时候，是值传递，要注意

时间复杂度  o(n), space o(1)

这个答案已经无法通过所有test， \[2,2,Integer max value],可以用更改后的code

```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 == null)
           return -1;
        
        int first = root.val;
        int second = Integer.MAX_VALUE;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            
            
            //node.val 必须是!= first，不能是>=
            //因为如果是>=的话，第一个node时候，second会被赋予 node的值，也就是最小值，最后second返回的是最小值
            if(node.val != first && node.val < second){
                second = node.val;
            }
            
            if(node.right != null){
                queue.offer(node.right);
            }
            
            if(node.left != null)
                queue.offer(node.left);
            
        }
        
        if(second == Integer.MAX_VALUE || second == first)
            return -1;
        else
            return second;

    }
    
    
    
    
}
```

```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 == null)
           return -1;
        
        int first = root.val;
        // int second = Integer.MAX_VALUE;
            int second = -1;        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            
            
            //node.val 必须是!= first，不能是>=
            //因为如果是>=的话，第一个node时候，second会被赋予 node的值，也就是最小值，最后second返回的是最小值
            // if(node.val != first && node.val <= second){
            //     second = node.val;
            // }
            
            if(node.val > first && (second == -1 || node.val < second)) {
                second = node.val;
            }
            
            // else if(node.val > first && node.val < second){
            //     second = node.val;
            // }
            
            if(node.right != null){
                queue.offer(node.right);
            }
            
            if(node.left != null)
                queue.offer(node.left);
            
        }
        
        if(second == -1)
            return -1;
        else
            return second;

    }
    
    
    
    
}
```

```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) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    find(root, pq);
    if (pq.size() < 2) return -1;
    pq.poll();
    return pq.poll();
  }
  
  public void find(TreeNode node, PriorityQueue<Integer> pq) {
    if (node == null) {
      return;
    }
    if (pq.isEmpty() || node.val != pq.peek()) {
      pq.add(node.val);
    }
    
    find(node.left, pq);
    find(node.right, pq);
  }
}
```