leetcode-671. 二叉树中第二小的节点刷题笔记（c++）

客官°小女子只卖身不卖艺 2023-02-21 11:57 82阅读 0赞

#### 写在前面 ####

*  难度：简单
 *  先序遍历 + set集合
    
     *  `set<int>::iterator`

#### 题目详情 ####

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
    
    给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
    
    示例 1:
    
    输入: 
        2
       / \
      2   5
         / \
        5   7
    
    输出: 5
    说明: 最小的值是 2 ，第二小的值是 5 。
    示例 2:
    
    输入: 
        2
       / \
      2   2
    
    输出: -1
    说明: 最小的值是 2, 但是不存在第二小的值。

#### ac代码 ####

*  解题思想
    
     *  先序遍历，存储节点至`set<int>`集合
     *  从`set（元素有序）`集合中取出第2大元素

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution
    {
        
    private:
        set<int> s;
        void preOrder(TreeNode* root)
        {
        
            if(!root)
                return;
            s.insert(root->val);
            preOrder(root->left);
            preOrder(root->right);
        }
    public:
        int findSecondMinimumValue(TreeNode* root)
        {
        
            preOrder(root);
            set<int>::iterator it = s.begin();
            if(s.size()>1)
                return *(++it);
            return -1;
        }
    };

*  参考文章
    
     *  [LeetCode 671. Second Minimum Node In a Binary Tree二叉树中第二小的节点 (C++)][LeetCode 671. Second Minimum Node In a Binary Tree_ _C]
     *

[LeetCode 671. Second Minimum Node In a Binary Tree_ _C]: https://www.cnblogs.com/silentteller/p/10903447.html