LeetCode.671.Second Minimum Node In a Binary Tree 求二叉树的次小值

题目描述

671 Second Minimum Node In a Binary Tree
https://leetcode-cn.com/problems/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 two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes. More formally, the property root.val = min(root.left.val, root.right.val) always holds.

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.

---

解题过程

求二叉树的次小值，没想到怎么利用 root.val = min(root.left.val, root.right.val) 性质
官方题解提示这个性质可以这样用：
如果 node.val > min1，我们知道在 node 处的子树中的所有值都至少是 node.val，因此在该子树中不此存在第二个最小值。
时间复杂度 O(n)，空间复杂度 O(n)

private static class SolutionV2020 {
    private Integer min;
    private Integer min2;
    public int findSecondMinimumValue(TreeNode root) {
        if (null == root) {
            return -1;
        }
        min = null;
        min2 = null;
        preOrderTraverse(root);
        return min2 != null ? min2 : -1;
    }

    private void preOrderTraverse(TreeNode root) {
        if (null == root) {
            return;
        }
        // 更新最小值
        if (null == min || root.val < min) {
            min2 = min;
            min = root.val;
        } else if (root.val > min && (min2 == null || root.val < min2)) {
            // 更新次小值
            min2 = root.val;
        }
        preOrderTraverse(root.left);
        preOrderTraverse(root.right);
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_671_SecondMinimumNodeInBinaryTree.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_671_SecondMinimumNodeInBinaryTree.java

---