leetcode-671-Second-Minimum-Node-In-a-Binary-Tree

描述

---

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.

分析

---

这道题目看起来跟 (M) Kth Smallest Element in a BST 类似，实际上不能直接套用其解法，因为这道题不考虑最小的数和第二小的数值相同的情况，也就是说排序后的结果每个数字只能出现一次。

解决方案1(Java)

---

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int min = Integer.MAX_VALUE;
    private int second = Integer.MAX_VALUE;
    
    public int findSecondMinimumValue(TreeNode root) {
        firstOrder(root);
        return (second == Integer.MAX_VALUE) ? -1: second;
    }
    
    private void firstOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.val < min) {
            second = min;
            min = root.val;
        } else if (root.val > min) {
            second = Math.min(second, root.val);
        }
        firstOrder(root.left);
        firstOrder(root.right);
    }
}

相关问题

---

• (M) Kth Smallest Element in a BST

题目来源