Java Recursive DFS Solution with explanation


  • 0

    After thinking about this problem carefully, you should find

    1. The value at the root is the smallest value.
    2. If one node's value is bigger than root, all the rest nodes in its subtree cannot be smaller than the value of that node.

    Since of that, starting from root, we search like this:
    If the child node's value is bigger than the root, we return that value and compare it to the result from the other child, return the min. Of course, at that time, the value of the other child equals to the root's value. Go deeper, and search the grandchildren. If there is a subtree with all the nodes having the root value, return Long.Max_VALUE (handling overflow).

    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) return -1;
        if (find(root) == Long.MAX_VALUE) return -1;
        else return (int)find(root);
    }
    private long find(TreeNode root) {
        if (root.left == null && root.right == null) return Long.MAX_VALUE;
        else {
            if (root.left.val == root.val) {
                if (root.right.val == root.val) {
                    return Math.min(find(root.left), find(root.right));
                }
                else return Math.min(find(root.left), root.right.val);
            }
            else {
                if (root.left.val == root.val) {
                    return Math.min(find(root.right), find(root.left));
                }
                else return Math.min(find(root.right), root.left.val);
            }
        }
    }

Log in to reply
 

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