Solution by azrush


  • 1
    A

    Approach #1 Simple tree traversal [Accepted]

    Algorithm

    Based on the problem description, the root node will always have the minimum value of the whole tree. This property also holds tree for any subtree. Now we can turn the problem to be "find the minimum value in the tree that is greater than the root's value -- call it min".

    In any subtree, as long as the root's value is greater than the min, then we don't need to look into that subtree anymore (because the bold property we have above). Otherwise, we need to look into the left and right subtree, and choose the minimum value that's greater than min.

    See more explanation in the comments below.

    Java

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public int findSecondMinimumValue(TreeNode root) {
            if (root == null) return -1;
            int min = root.val;
            int res = helper(root, min);
            return res == Integer.MAX_VALUE ? -1 : res;
        }
    
        private int helper(TreeNode n, int min) {
            if (n == null) return Integer.MAX_VALUE;
    
            // If n.val > min, then just return,
            // because n.val will be the mimimum value of the current subtree.
            if (n.val > min) return n.val;
    
            // If n.val is not > min, then n.val == min.
            // Remember min is the global minimum.
            if (n.left != null && n.right != null) {
                return Math.min(helper(n.left, min), helper(n.right, min));
            }
    
            // Don't return -1 here.
            return Integer.MAX_VALUE;
        }
    }
    

    Complexity Analysis

    • Time complexity : Averagely $$O(depth)$$, worst case $$O(n)$$.

    Averagely, it will only need to traverse the depth of the tree to find the result. In worst case (where all the nodes have the same value as min), it will need to visit every node to find the result.


Log in to reply
 

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