C++, DFS recursion


  • 15
    Z

    This question is very similar to searching for minimum value in the Binary Tree.
    The only requirement is that this value must be different from the root value, k.

    If the root value of a subtree == k, 
             keep searching its children.
    else, 
             return the root value because it is the minimum of current subtree.
    
    class Solution {
    public:
        int findSecondMinimumValue(TreeNode* root) {
            if (!root) return -1;
            int ans = minval(root, root->val);
            return ans;
        }
    private:
        int minval(TreeNode* p, int first) {
            if (p == nullptr) return -1;
            if (p->val != first) return p->val;
            int left = minval(p->left, first), right = minval(p->right, first);
            // if all nodes of a subtree = root->val, 
            // there is no second minimum value, return -1
            if (left == -1) return right;
            if (right == -1) return left;
            return min(left, right);
        }
    };
    

  • 1

    Not optimal but easy to code. Could be a naive one !

    class Solution {
    public:
        set<int> dict;
        int findSecondMinimumValue(TreeNode* root) {
            preorder(root);
            return dict.size()<=1?-1:*(++dict.begin());
        }
        
        void preorder(TreeNode* root){
            if (!root) return;
            dict.insert(root->val);
            preorder(root->left);
            preorder(root->right);
        }
    };
    

  • 0
    X

    @zestypanda
    There is a corner case:
    For Example:
    Input:
    [1,1,2147483647]
    Your answer: -1
    Excepted answer: 2147483647


  • 0
    Z

    @xpfxzxc Thanks for the comments. There was a note in my code explanation.
    "I use INT_MAX to simplify the code. If you are concerned that INT_MAX is the second minimum of the tree, feel free to use -1 and make associated changes."

    I also updated the code. I hope you are happy with this version.


  • 2

    Here's the java.

    public int findSecondMinimumValue(TreeNode root) {
        if(root == null) return -1;
    
        int l = (root.left != null && root.left.val != root.val) ? root.left.val :findSecondMinimumValue(root.left);
        int r = (root.right != null && root.right.val != root.val) ? root.right.val :findSecondMinimumValue(root.right);
    
        if(l == -1 || r == -1) return Math.max(l, r);
        return Math.min(l, r);
    }

Log in to reply
 

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