671. 二叉树中第二小的节点（递归）

我不是女神ヾ 2023-10-05 02:55 23阅读 0赞

#### 671. 二叉树中第二小的节点 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。

更正式地说，root.val = min(root.left.val, root.right.val) 总成立。

给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]

## 解题思路 ##

该题很容易想到遍历树，然后用set来保存。取set中第下标1即是第二小的值。要注意使用`treeSet<>`，因为`hashSet<>`不保证有序。

## 代码 ##

class Solution {
        
        Set<Integer> set = new TreeSet<>();
    
        public int findSecondMinimumValue(TreeNode root) {
        
            if (root == null) {
        
                return -1;
            }
    
            traverseTree(root);
            int res = -1;
            if (set.size() > 0) {
        
                List<Integer> list = new ArrayList<>(set);
                if(set.size()>=2){
        
                    res = list.get(1);
                }
            }
    
            return res;
        }
    
    
        public void traverseTree(TreeNode root) {
        
            if (root == null) {
        
                return;
            }
    
            set.add(root.val);
            traverseTree(root.left);
            traverseTree(root.right);
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210115220700617.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210115220710770.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70