c++ o(n) bfs & dfs solutions


  • 0
    Z

    dfs

    class Solution {
    public:
        int findSecondMinimumValue(TreeNode* root) {
            set<int> s;
            dfs(root, s);
            s.erase(s.begin());
            return s.empty() ? -1 : *s.begin();
        }
    
        void dfs(TreeNode * p, set<int> & s) {
            if ( p ) {
                s.insert(p->val);
                dfs(p->left, s);
                dfs(p->right, s);
            }
        }
    };
    
    // Runtime: 3 ms
    

    bfs

    class Solution {
    public:
        int findSecondMinimumValue(TreeNode* root) {
            set<int> s;
            queue<TreeNode *> q;
            q.push(root);
            while ( ! q.empty() ) {
                auto p = q.front();
                q.pop();
                s.insert(p->val);
                if ( p->left )
                    q.push(p->left);
                if ( p->right )
                    q.push(p->right);
            }
            s.erase(s.begin());
            return s.empty() ? -1 : *s.begin();
        }
    };
    
    // 34 / 34 test cases passed.
    // Status: Accepted
    // Runtime: 3 ms
    

Log in to reply
 

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