Very simple Java solution


  • 5
    public int findSecondMinimumValue(TreeNode root) {
                if (root == null) {
                    return -1;
                }
                Set<Integer> set = new TreeSet<>();
                dfs(root, set);
                Iterator<Integer> iterator = set.iterator();
                int count = 0;
                while (iterator.hasNext()) {
                    count++;
                    int result = iterator.next();
                    if (count == 2) {
                        return result;
                    }
                }
                return -1;
            }
    
            private void dfs(TreeNode root, Set<Integer> set) {
                if (root == null) {
                    return;
                }
                set.add(root.val);
                dfs(root.left, set);
                dfs(root.right, set);
                return;
            }
    

    Also viewable here on Github.


  • 1
    P

    nice use of TreeSet to keep elements in ascending order.


  • 0
    O

    you do not need to dfs through all nodes in the tree. (why?)

    Values of all children of a node are equal or bigger than its value. So, if a node value is a candidate for 2nd min, we can trim all its children and ignore them. They are simply equal or bigger.


  • 3

    Had same idea but a bit shorter version for the iterator handling

    public int findSecondMinimumValue(TreeNode root) {
            if ((root == null) || (root.left == null && root.right == null)) 
                return -1;
            
            Set<Integer> set = new TreeSet<>();
            dfs(root, set);
            Iterator<Integer> it = set.iterator();
            it.next();
            return (it.hasNext()) ? it.next() : -1;
        }
        private void dfs(TreeNode root, Set<Integer> set) {
            if (root == null) return;
            set.add(root.val);
            dfs(root.left, set);
            dfs(root.right, set);
        }
    

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

  • 1
    M

    This is O(n log n)?


  • 0

    @macrohard Right, per Java doc, add operation is logn, traversing the entire tree is n, so total O(nlogn). Thanks.


  • 0
    F

    My dfs version:

    class Solution {
        int min2 = Integer.MAX_VALUE;
        public int findSecondMinimumValue(TreeNode root) {
            dfs(root, root.val);
            return min2 == Integer.MAX_VALUE? -1 : min2;
        }
        public void dfs(TreeNode root, int min) {
            if (root == null) {
                return;
            }
            if (root.val != min &&  root.val - min < min2 - min) {
                min2 = root.val;
            }
            dfs(root.left, min);
            dfs(root.right, min);
        }
    }
    

Log in to reply
 

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