C++, DFS recursion


  • 16
    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);
        }
    };
    

  • 2

    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);
    }

  • 0
    M

    @zestypanda I think question test cases are wrong.
    For example : for this binary tee [2,5,3], output should be 3, instead of 5.
    After running leetcode test run, i am getting 5 as the expected answer.


  • 0
    Z

    @mohitverma3222 your example is not binary search tree


  • 0
    F

    I don't understand how this works. If you have a tree like so

        10
       /  \ 
      8    11
     / \
     6  9
    /  \
    5   7
    

    your code would not work? You would return 8 but the proper answer would be 6


  • 0
    Z

    @felder Note the problem states "this node's value is the smaller value among its two sub-nodes". Your test case is not valid.


Log in to reply
 

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