671. Second Minimum Node In a Binary Tree

缺乏、安全感 2022-06-08 14:07 129阅读 0赞

题目描述

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.

解题思路：

这个题目首先遍历一遍求出最大值，然后将min与min\_next赋值给最大值。然后二次遍历，找到次小值就可以了。

时间复杂度是O（n）

解答代码：

/\*\*  
 \* 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 min,minn=-1;  
      
    void get\_minn(TreeNode\* root)  
    \{  
        if(root)  
        \{  
            if(minn < root->val)  
                min = minn = root->val;  
            get\_minn(root->left);  
            get\_minn(root->right);  
        \}  
    \}  
      
    void preorder(TreeNode\* root)  
    \{  
        if(root)  
        \{  
            if(root->val < min )  
            \{  
                minn = min;  
                min = root->val;  
            \}  
            if(root->val <minn && root->val >min)  
                minn = root->val;  
              
            preorder(root->left);  
            preorder(root->right);  
        \}  
    \}  
    int findSecondMinimumValue(TreeNode\* root) \{  
        if( root==NULL || (root->left==NULL&&root->right==NULL&&root!=NULL) )  
            return -1;  
        int min = root->val;  
          
        get\_minn(root);  
          
        preorder(root);  
          
        if(minn == min)  
            return -1;          
          
        return minn;  
    \}  
      
\};