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.


  • 2

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

  • 1
    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.


Log in to reply
 

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