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

Michael阿明

发布于 2021-02-20 14:22:03

50000

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

1. 题目信息

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

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

示例 1:

输入: 
    2
   / \
  2   5
     / \
    5   7

输出: 5
说明: 最小的值是 2 ，第二小的值是 5 。
示例 2:

输入: 
    2
   / \
  2   2

输出: -1
说明: 最小的值是 2, 但是不存在第二小的值。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

根节点是最小的，依次查找每个节点是否比最小的大
并更新找到的第二小的数组

2.1 递归查找

class Solution {
public:
    int findSecondMinimumValue(TreeNode* root) {
        if(!root)
        	return -1;
        int minNum = root->val;
        long secMinNum = LONG_MAX;
        findSec(root,minNum,secMinNum);
        if(secMinNum != LONG_MAX)
        	return secMinNum;
        return -1;
    }

    void findSec(TreeNode* root, int &minNum, long &secMinNum)
    {
    	if(!root)
    		return;
    	if(root->val > minNum && root->val < secMinNum)
    	{
    		secMinNum = root->val;
    	}
    	findSec(root->left,minNum,secMinNum);
        findSec(root->right,minNum,secMinNum);
    }
};

2.2 改循环

前序循环

class Solution {
public:
    int findSecondMinimumValue(TreeNode* root) {
        if(!root)
        	return -1;
        int minNum = root->val;
        long secMinNum = LONG_MAX;
        stack<TreeNode*> stk;
        while(root || !stk.empty())
        {
        	while(root)
        	{
        		stk.push(root);
        		if(root->val > minNum && root->val < secMinNum)
        			secMinNum = root->val;
        		root = root->left;
        	}
        	root = stk.top()->right;
        	stk.pop();
        }
        if(secMinNum != LONG_MAX)
        	return secMinNum;
        return -1;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/09/05 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树