Second Minimum Node In a Binary Tre

题目：二叉树中第二小的节点

解决方法

方法一

思路

用深度优先搜索遍历此二叉树，同时利用Set结构(具有唯一性)记录树中每个不一样的值。然后从set中找到第二小的值。
最小的节点一定是二叉树的根节点。

代码示例

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);//二叉树前序遍历所有结点并添加到hashset集合中，去重

        int min = root.val;//根据题目的限定条件，根节点是整个二叉树的最小值
        long ans = Long.MAX_VALUE;
        for (int v : uniques) {
            if (min < v && v < ans) {//遍历集合，找到第二小的值
                ans = v;
            }
        }
        //return ans == Long.MAX_VALUE ? -1 : (int) ans;
        return ans < Long.MAX_VALUE ? (int) ans : -1;//如果ans小于Long.MAX_VALUE说明找到了第二小的值
    }
}

复杂度分析

N是给定的树中的所有结点的数量
时间复杂度：O(N)。
空间复杂度：O(N)。

方法二

思路

基于方法一的优化。
让min = root.val，当遍历树的节点时，如果node.val > min，结合题意我们可以推测出，在子树中的所有值都是大于等于node.val ，这个值就是我们想要的答案，所以我们没有必要在搜索子树。

我们只关心第二小的值，我们不需要记录任何比当前候选值大的值，所以我们可以不需要像方法一那样，通过set结构保存所有的值。

代码示例

复杂度分析

时间复杂度：O(N)，我们需要访问每个节点最多一次。
空间复杂度：O(N)。