Share my 3ms java solution with explanations.


  • 0
    S

    The idea is: look for which side (left subtree or right subtree) to go, and discard the subtree that you know for sure won't affect the result.

    Base cases:
    (a) if root is null, or root is the only node in the tree, then return -1 as there is no second smallest node.
    (b) if there are only three nodes (root, root.left, root.right) in the tree, then we can easily determine which is the second smallest: if all three nodes are equal, return -1. Otherwise, the second smallest is the larger one between root.left and root.right

    Recursion:
    There are three cases
    (1) root.val == root.left.val == root.right.val
    This is most complicated since the second smallest value could lay in both subtrees. For example, [2,2,2,2,5] and [2,2,2,null,null,2,5]. Therefore we need to find second smallest value of both the left subtree and the right subtree, and return the smaller one between the two. Note a special case: if there is no second smallest number of the left subtree (or the right subtree), then we need to return the second smallest number of the right subtree(or the left subree). Example is [2,2,2,2,2,2,5]

    (2)root.val == root.left.val, but root.val < root.right.val
    The second smallest value could only be the second smallest value of the left subtree, or root.right.val. So we don't need to traverse the right subtree.

    (3) root.val == root.right.val but root.val < root.left.val
    Similar to case (2), the second smallest value could only be the second smallest value of the right subtree, or root.left.val. So we don't need to traverse the left subtree.

    Time complexity: O(lgN) on average (no need to traverse one of the subtrees at each step), O(n) in worst case (always hit case (1))

    Space complexity: O(lgN) on average and O(n) in worst case. (count how many recursions would be called)

    The code is:

    public int findSecondMinimumValue(TreeNode root) {
            if(root == null || root.left == null){
                return -1;
            }else if(root.left.left == null && root.right.left == null){
                //only 3 nodes according to the question, easy to determine what is the second smallest value
                if(root.left.val == root.right.val)     return -1;
                else    return Math.max(root.left.val, root.right.val);
            }else if(root.val == root.left.val && root.val == root.right.val){
                //root is the smallest, find the second smallest from both subtrees (namely x and y), return the smaller of x and y
                int leftSec = findSecondMinimumValue(root.left);
                int rightSec = findSecondMinimumValue(root.right);
                if(leftSec == -1)   return rightSec;
                else if(rightSec == -1)     return leftSec;
                else    return Math.min(leftSec, rightSec);
            }else if(root.val == root.left.val){
                //must have root.right.val > root.val
                int leftSec = findSecondMinimumValue(root.left);
                if(leftSec == -1)   return root.right.val;
                else return Math.min(leftSec, root.right.val);
            }else{
                //must have root.val == right.right.val, and root.left.val > root.val
                int rightSec = findSecondMinimumValue(root.right);
                if(rightSec == -1)  return root.left.val;
                else return Math.min(rightSec, root.left.val);
            }
        }
    

Log in to reply
 

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