Java DFS solution

  • 0

    This problem can be solved by divide and conquer. For a TreeNode root, there are 3 cases:
    (1) root == null, return -1;
    (2) root has no children, then the second minimum value does not exist, return -1 as well;
    (3) root has 2 children: left and right. Let's first assume left.val < right.val. If left doesn't have any children, right.val is what we want since right.val is the max value in the right subtree and right.val is greater than left.val.
    If left has two children, we need compare the second minimum value of the left subtree and the minimum value of the right subtree. The smaller value is the second minimum value of the tree.
    If left.val == right.val, we need to compare the second minimum values of the both subtrees.

     public int findSecondMinimumValue(TreeNode root) {
            if (root == null) return -1;
            if (root.left == null && root.right == null) return -1;
            int leftR = root.left.val;
            int rightR = root.right.val;
            if (root.left.val < root.right.val) {
                leftR = findSecondMinimumValue(root.left);
            } else if (root.left.val > root.right.val) {
                rightR = findSecondMinimumValue(root.right);
            } else {
                leftR = findSecondMinimumValue(root.left);
                rightR = findSecondMinimumValue(root.right);
            if (leftR == -1 && rightR == -1) return -1;
            else if (leftR == -1) return rightR;
            else if (rightR == -1) return leftR;
            return Math.min(leftR, rightR);

Log in to reply

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