文章目录

• 一【题目类别】
• 二【题目难度】
• 三【题目编号】
• 四【题目描述】
• 五【题目示例】
• 六【解题思路】
• 七【题目提示】
• 八【时间频度】
• 九【代码实现】
• 十【提交结果】

一【题目类别】

• 深度优先搜索

二【题目难度】

• 简单

三【题目编号】

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

四【题目描述】

• 给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
• 更正式地说，即 root.val = min(root.left.val, root.right.val) 总成立。
• 给出这样的一个二叉树，你需要输出所有节点中的 第二小的值 。
• 如果第二小的值不存在的话，输出 -1 。

五【题目示例】

• 示例 1：

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

• 示例 2：

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

六【解题思路】

• 分析题目后我们可以发现，根节点值是整个二叉树中最小的，因为它是左右子树值的最小值，所以我们可以将题目转化为求左右子树的最小值，这样问题思路就清晰了：
  • 如果在遍历过程中有某个节点值大于根节点值，直接返回即可，因为按顺序遍历下来，第一个遇到的大于根结点值的节点值肯定是最小的
  • 然后获取左右子树的最小值
  • 如果左右子树的最小值都存在，按照题目要求，我们要取整棵树中第二小的值，所以返回两者中最小的
  • 如果左右子树的最小值都不存在，按照题目要求，返回-1
  • 如果左右子树的最小值有一个不存在，按照题目要求，返回另一个存在的，也就是返回两者中的最大值
• 最后返回结果即可

七【题目提示】

• 树中节点数目在范围[1,25]内树中节点数目在范围 [1, 25] 内树中节点数目在范围[1,25]内
• 1<=Node.val<=231−11 <= Node.val <= 2^{31} - 11<=Node.val<=231−1
• 对于树中每个节点root.val==min(root.left.val,root.right.val)对于树中每个节点 root.val == min(root.left.val, root.right.val)对于树中每个节点root.val==min(root.left.val,root.right.val)

八【时间频度】

• 时间复杂度：O(n)O(n)O(n)，其中nnn为传入二叉树的节点个数
• 空间复杂度：O(n)O(n)O(n)，其中nnn为传入二叉树的节点个数

九【代码实现】

1. Java语言版

class Solution {public int dfs(TreeNode root,int minVal){if(root == null){return -1;}if(root.val > minVal){return root.val;}int left = dfs(root.left,minVal);int right = dfs(root.right,minVal);if(left >= 0 && right >= 0){return Math.min(left,right);}return Math.max(left,right);}public int findSecondMinimumValue(TreeNode root) {return dfs(root,root.val);}
}

2. C语言版

int dfs(struct TreeNode* root,int minVal)
{if(root == NULL){return -1;}if(root->val > minVal){return root->val;}int left = dfs(root->left,minVal);int right = dfs(root->right,minVal);if(left >= 0 && right >= 0){return fmin(left,right);}return fmax(left,right);
}int findSecondMinimumValue(struct TreeNode* root)
{return dfs(root,root->val);
}

3. Python语言版

class Solution:def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:def dfs(root,minVal):if root is None:return -1if root.val > minVal:return root.valleft = dfs(root.left,minVal)right = dfs(root.right,minVal)if left >= 0 and right >= 0:return min(left,right)return max(left,right)return dfs(root,root.val)

4. C++语言版

class Solution {
public:int dfs(TreeNode* root,int minVal){if(root == nullptr){return -1;}if(root->val > minVal){return root->val;}int left = dfs(root->left,minVal);int right = dfs(root->right,minVal);if(left >= 0 && right >= 0){return min(left,right);}return max(left,right);}int findSecondMinimumValue(TreeNode* root) {return dfs(root,root->val);}
};

十【提交结果】

1. Java语言版
   

2. C语言版
   

3. Python语言版
   

4. C++语言版