Java divide and conquer solution


  • 7
    T

    for left and right sub-node, if their value is the same with the parent node value, need to using recursion to find the next candidate, otherwise use their node value as the candidate.

    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) {
            return -1;
        }
        if (root.left == null && root.right == null) {
            return -1;
        }
        
        int left = root.left.val;
        int right = root.right.val;
        
        // if value same as root value, need to find the next candidate
        if (root.left.val == root.val) {
            left = findSecondMinimumValue(root.left);
        }
        if (root.right.val == root.val) {
            right = findSecondMinimumValue(root.right);
        }
        
        if (left != -1 && right != -1) {
            return Math.min(left, right);
        } else if (left != -1) {
            return left;
        } else {
            return right;
        }
    }
    

  • 0
    E
    This post is deleted!

  • 0

    @ttZack Concise solution

    public int findSecondMinimumValue(TreeNode root) {
        if(root==null)  return -1;
        return findSecondMinValue(root, root.val);
    }
    
    
    public int findSecondMinValue(TreeNode root, int min) {
        if(root==null)  return -1;
        if(root.val>min)   return root.val;
        int leftMin = findSecondMinValue(root.left,min);
        int rightMin = findSecondMinValue(root.right,min);
        return (leftMin==-1 || rightMin==-1) ? Math.max(leftMin,rightMin) : Math.min(leftMin,rightMin);
    }

  • 0
    T

    Is the running time be O(n) where n is the number of nodes in the tree?


Log in to reply
 

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