Solution by awice


  • 0

    Approach #1: Brute Force [Accepted]

    Intuition and Algorithm

    Traverse the tree with a depth-first search, and record every unique value in the tree using a Set structure uniques.

    Then, we'll look through the recorded values for the second minimum. The first minimum must be root.val.

    Java

    class Solution {
        public void dfs(TreeNode root, Set<Integer> uniques) {
            if (root != null) {
                uniques.add(root.val);
                dfs(root.left, uniques);
                dfs(root.right, uniques);
            }
        }
        public int findSecondMinimumValue(TreeNode root) {
            Set<Integer> uniques = new HashSet<Integer>();
            dfs(root, uniques);
    
            int min1 = root.val;
            long ans = Long.MAX_VALUE;
            for (int v : uniques) {
                if (min1 < v && v < ans) ans = v;
            }
            return ans < Long.MAX_VALUE ? (int) ans : -1;
        }
    }
    

    Python

    class Solution(object):
        def findSecondMinimumValue(self, root):
            def dfs(node):
                if node:
                    uniques.add(node.val)
                    dfs(node.left)
                    dfs(node.right)
    
            uniques = set()
            dfs(root)
    
            min1, ans = root.val, float('inf')
            for v in uniques:
                if min1 < v < ans:
                    ans = v
    
            return ans if ans < float('inf') else -1
    

    Complexity Analysis

    • Time Complexity: $$O(N)$$, where $$N$$ is the total number of nodes in the given tree. We visit each node exactly once, and scan through the $$O(N)$$ values in unique once.

    • Space Complexity: $$O(N)$$, the information stored in uniques.


    Approach #2: Ad-Hoc [Accepted]

    Intuition and Algorithm

    Let min1 = root.val. When traversing the tree at some node node, if node.val > min1, we know all values in the subtree at node are at least node.val, so there cannot be a better candidate for the second minimum in this subtree. Thus, we do not need to search this subtree.

    Also, as we only care about the second minimum ans, we do not need to record any values that are larger than our current candidate for the second minimum, so unlike Approach #1 we can skip maintaining a Set of values entirely.

    Java

    class Solution {
        int min1;
        long ans = Long.MAX_VALUE;
    
        public void dfs(TreeNode root) {
            if (root != null) {
                if (min1 < root.val && root.val < ans) {
                    ans = root.val;
                } else if (min1 == root.val) {
                    dfs(root.left);
                    dfs(root.right);
                }
            }
        }
        public int findSecondMinimumValue(TreeNode root) {
            min1 = root.val;
            dfs(root);
            return ans < Long.MAX_VALUE ? (int) ans : -1;
        }
    }
    

    Python

    def findSecondMinimumValue(self, root):
        self.ans = float('inf')
        min1 = root.val
    
        def dfs(node):
            if node:
                if min1 < node.val < self.ans:
                    self.ans = node.val
                elif node.val == min1:
                    dfs(node.left)
                    dfs(node.right)
    
        dfs(root)
        return self.ans if self.ans < float('inf') else -1
    

    Complexity Analysis

    • Time Complexity: $$O(N)$$, where $$N$$ is the total number of nodes in the given tree. We visit each node at most once.

    • Space Complexity: $$O(N)$$. The information stored in ans and min1 is $$O(1)$$, but our depth-first search may store up to $$O(h) = O(N)$$ information in the call stack, where $$h$$ is the height of the tree.


Log in to reply
 

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