題目：二叉樹中第二小的節(jié)點

解決方法

方法一

思路

用深度優(yōu)先搜索遍歷此二叉樹，同時利用Set結構(具有唯一性)記錄樹中每個不一樣的值。然后從set中找到第二小的值。
最小的節(jié)點一定是二叉樹的根節(jié)點。

代碼示例

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;//根據題目的限定條件，根節(jié)點是整個二叉樹的最小值
        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)。

方法二

思路

基于方法一的優(yōu)化。
讓min = root.val，當遍歷樹的節(jié)點時，如果node.val > min，結合題意我們可以推測出，在子樹中的所有值都是大于等于node.val ，這個值就是我們想要的答案，所以我們沒有必要在搜索子樹。

我們只關心第二小的值，我們不需要記錄任何比當前候選值大的值，所以我們可以不需要像方法一那樣，通過set結構保存所有的值。

代碼示例

復雜度分析

時間復雜度：O(N)，我們需要訪問每個節(jié)點最多一次。
空間復雜度：O(N)。