LeetCode 671 - Second Minimum Node In a Binary Tree

https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/description/

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly twoor zero sub-node. If the node has two sub-nodes, then this node's value is the smaller value among its two sub-nodes.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes' value in the whole tree.

If no such second minimum value exists, output -1 instead.

Example 1:

Input: 
    2
   / \
  2   5
     / \
    5   7

Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.

Example 2:

Input: 
    2
   / \
  2   2

Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.

X. https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/discuss/107233/Java-4-lines

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

https://segmentfault.com/a/1190000017125308

    public int findSecondMinimumValue(TreeNode root) {
        if(root == null || root.left == null) return -1;
        
        int leftRes, rightRes;
        if (root.left.val == root.val) {
            leftRes = findSecondMinimumValue(root.left);
        } else {
            leftRes = root.left.val;
        }
        if (root.right.val == root.val) {
            rightRes = findSecondMinimumValue(root.right);
        } else {
            rightRes = root.right.val;
        }
        
        if (leftRes == -1 && rightRes == -1) return -1;
        else if (leftRes == -1) return rightRes;
        else if (rightRes == -1) return leftRes;
        else return Math.min(leftRes, rightRes);
    }

http://www.voidcn.com/article/p-ocfqevvg-bnu.html

对于左结点和右结点, 如果它们的值都和父结点的值一样的话，继续递归左结点和右结点。
如果它们的值并不是都和父结点的值一样，那么哪个不一样，结果就取哪个的值。如果两个都不一样，那么取两者中较小的那个。

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

X. https://zxi.mytechroad.com/blog/leetcode/leetcode-671-second-minimum-node-in-a-binary-tree/

    // Return the second smallest number in the (sub-tree)

    // s1 is the smallest value

    int DFS(TreeNode* root, int s1) {

        if(!root) return -1;

        

        // If root's value is already grater than s1,

        // then all its children's value should be >= s1.

        // Thus root's value is the second smallest one.

        // No need to visit the

        if(root->val > s1) return root->val;

        

        int sl = DFS(root->left, s1);

        int sr = DFS(root->right, s1);

        

        if(sl == -1) return sr;

        if(sr == -1) return sl;

        

        // Return the smaller one among two subtrees

        return min(sl, sr);

    }

http://www.cnblogs.com/grandyang/p/7590156.html

这道题让我们找二叉树中的第二小的结点值，并且给该二叉树做了一些限制，比如对于任意一个结点，要么其没有子结点，要么就同时有两个子结点，而且父结点值是子结点值中较小的那个，当然两个子结点值可以相等。那么直接上暴力搜索呗，根据该树的附加条件可知，根结点一定是最小的结点值first，那么我们只要找出第二小的值second即可，初始化为整型的最大值。然后对根结点调用递归函数，将first和second当作参数传进去即可。在递归函数中，如果当前结点为空，直接返回，若当前结点孩值不等于first，说明其肯定比first要大，然后我们看其是否比second小，小的话就更新second，然后对当前结点的左右子结点分别调用递归函数即可，参见代码如下：

    int findSecondMinimumValue(TreeNode* root) {
        int first = root->val, second = INT_MAX;
        helper(root, first, second);
        return (second == first || second == INT_MAX) ? -1 : second;
    }
    void helper(TreeNode* node, int& first, int& second) {
        if (!node) return;
        if (node->val != first && node->val < second) {
            second = node->val;
        }
        helper(node->left, first, second);
        helper(node->right, first, second);
    }

下面这种方法也是用递归来做的，不过现在递归函数有了返回值，在递归函数中，还是先判断当前结点是否为空，为空直接返回-1。然后就是看当前结点是否等于first，不等于直接返回当前结点值。如果等于，我们对其左右子结点分别调用递归函数，分别得到left和right。如果left和right其中有一个为-1了，我们取其中的较大值；如果left和right都不为-1，我们取其中的较小值返回即可，参见代码如下：

    int findSecondMinimumValue(TreeNode* root) {
        return helper(root, root->val);
    }
    int helper(TreeNode* node, int first) {
        if (!node) return -1;
        if (node->val != first) return node->val;
        int left = helper(node->left, first), right = helper(node->right, first);
        return (left == -1 || right == -1) ? max(left, right) : min(left, right);
    }

下面这种递归方法更加简洁了，没有再使用专门的递归函数helper，而是对当前根结点判断其左子树是否存在，不存在就返回-1。题目中说了是非空树，所以根结点一定存在。然后我们比较如果左子结点值等于根结点值，我们则对其左子结点调用递归函数；否则left就等于其左子结点值。再比较如果右子结点值等于根结点值，则对其右子结点调用递归函数；否则right就等于其右子结点值。最后我们还是看如果left和right其中有一个为-1了，我们取其中的较大值；如果left和right都不为-1，我们取其中的较小值返回即可，参见代码如下：

    int findSecondMinimumValue(TreeNode* root) {
        if (!root->left) return -1;
        int left = (root->left->val == root->val) ? findSecondMinimumValue(root->left) : root->left->val;
        int right = (root->right->val == root->val) ? findSecondMinimumValue(root->right) : root->right->val;
        return (left == -1 || right == -1) ? max(left, right) : min(left, right);
    }

整了三种递归的解法，来看一种迭代的解法吧，用的是层序遍历，但还是用的解法一种的不停更新second的方法，参见代码如下：

    int findSecondMinimumValue(TreeNode* root) {
        int first = root->val, second = INT_MAX;
        queue<TreeNode*> q{{root}};
        while (!q.empty()) {
            auto t = q.front(); q.pop();
            if (t->val != first && t->val < second) {
                second = t->val;
            }
            if (t->left) q.push(t->left);
            if (t->right) q.push(t->right);
        }
        return (second == first || second == INT_MAX) ? -1 : second;
    }

Let $\text{min1 = root.val}$. When traversing the tree at some node, $\text{node}$, if node.val > min1$\text{node.val > min1}$, we know all values in the subtree at $\text{node}$ are at least $\text{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 $\text{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(uniques) entirely.

• 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 $\text{ans}$ and $\text{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.

  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;

  }

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

  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;

  }