Solution by <644367822>


  • 0
    6

    Approach #1 Duplicate removal [ Accepted ]

    Algorithm

    We can use the STL function set<int> to save the element. It will sort the element and remove duplicate.

    c++

    
    class Solution {
    public:
        void dfs( TreeNode *root){
            if( root ){
                slist.insert( root->val) ;
                dfs(root->left);
                dfs(root->right);
            }
        }
        int findSecondMinimumValue(TreeNode* root) {
            dfs(root);
            if( slist.size()<=1){
                return -1;
            }
            int  count =0;
            for( auto it = slist.begin() ; it!=slist.end() ; it++) {
                count++;
                if(  count ==2){
                    return *it;
                }
            }
            return 0;
        }
    private:
        set<int> slist;
    };
    

    Complexity Analysis

    • Time complexity : $O(N*logN)$.

    • Space complexity : $O(N)$.

    Approach #2 Two record val [ Accepted ]

    Algorithm

    We create two values to record the minimum value and the second minimum value .
    Maintain and update them .

    c++

    class Solution {
    public:
        void dfs( TreeNode * root ){
            if( root ){
                if(root->val<=minimum){
                    minimum = root->val;
                }
                else{
                    if(root->val<=second_min){
                        second_min = root->val;
                    }
                }
                dfs(root->left);
                dfs(root->right);
            }
        }
        int findSecondMinimumValue(TreeNode* root) {
            dfs(root);
            if(second_min == INT_MAX){
                return -1;
            }
            return second_min;
        }
    private:
        int minimum = INT_MAX;
        int second_min = INT_MAX;
    };
    

    Complexity Analysis

    • Time complexity : $O(N)$. We only travelsal the tree once.

    • Space complexity : $O(1)$.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.