( “树” 之 DFS) 671. 二叉树中第二小的节点 ——【Leetcode每日一题】

╰半夏微凉° 2024-03-23 13:29 69阅读 0赞

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

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

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

给出这样的一个二叉树，你需要输出所有节点中的 **第二小的值** 。

如果第二小的值不存在的话，输出 -1 。

##### 示例 1: #####

![在这里插入图片描述][08e9e294e144490aa82c8d9227a9e6df.png]

> 输入：root = \[2,2,5,null,null,5,7\]  
> 输出：5  
> 解释：最小的值是 2 ，第二小的值是 5 。

##### 示例 2: #####

![在这里插入图片描述][f6bfb49b4d2247049c046cb4fe02754f.png]

> 输入：root = \[2,2,2\]  
> 输出：-1  
> 解释：最小的值是 2, 但是不存在第二小的值。

**提示：**

*  树中节点数目在范围 \[1, 25\] 内
 *   1 < = N o d e . v a l < = 2 31 − 1 1 <= Node.val <= 2^\{31\} - 1 1<=Node.val<=231−1
 *  对于树中每个节点 `root.val == min(root.left.val, root.right.val)`

#### 思路：DFS ####

由`root.val = min(root.left.val, root.right.val)`，所以根节点一定是最小值，

要找所有节点中的 **第二小的值**，一定在根节点左右节点中第一个出现的不与根节点相等的值, 取最小值即为**第二小的值**。

#### 代码：(Java、C++) ####

**Java**

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public int findSecondMinimumValue(TreeNode root) {
        
            if(root == null) return -1;
            int leftval = -1;
            int rightval = -1;
            if(root.left != null && root.left.val != root.val) {
        
                leftval = root.left.val;
            }else{
        
                leftval = findSecondMinimumValue(root.left);
            }
            if(root.right != null && root.right.val != root.val) {
        
                rightval = root.right.val;
            }else{
        
                rightval = findSecondMinimumValue(root.right);
            }
            if(leftval == -1) return rightval;
            if(rightval == -1) return leftval;
            
            return Math.min(leftval, rightval); 
        }
    }

**C++**

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
        
    public:
        int findSecondMinimumValue(TreeNode* root) {
        
            if(root == NULL) return -1;
            int leftval = -1;
            int rightval = -1;
            if(root->left != NULL && root->left->val != root->val) {
        
                leftval = root->left->val;
            }else{
        
                leftval = findSecondMinimumValue(root->left);
            }
            if(root->right != NULL && root->right->val != root->val) {
        
                rightval = root->right->val;
            }else{
        
                rightval = findSecondMinimumValue(root->right);
            }
            if(leftval == -1) return rightval;
            if(rightval == -1) return leftval;
            
            return min(leftval, rightval); 
        }
    };

##### 运行结果： #####

![在这里插入图片描述][cc411a2a7dac478f94c02e90cde7a9ae.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ) O(n) O(n)，其中 `n` 为树的结点数目，我们最多需要对整棵二叉树进行一次遍历。
 *  **空间复杂度**： O ( n ) O(n) O(n)。递归栈最坏情况下需要 O ( n ) O(n) O(n)的空间。

题目来源：[力扣。][Link 1]

> 放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！  
> 关注我 [leetCode专栏][leetCode]，每日更新！

##### 注： 如有不足，欢迎指正！ #####

[08e9e294e144490aa82c8d9227a9e6df.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/626c1fda831f49f98292c493fcf87b00.png
[f6bfb49b4d2247049c046cb4fe02754f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/45f81694fd9e4480a83ef753742f96f9.png
[cc411a2a7dac478f94c02e90cde7a9ae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/defba6d80fba4228a81d4b0de0d4bb20.png
[Link 1]: https://leetcode.cn/problems/second-minimum-node-in-a-binary-tree/description/
[leetCode]: http://t.csdn.cn/kQLJO