找出该树中第二小的值--思路及算法实现

  在二叉树中最重要的操作莫过于遍历,即按照某一顺序访问树中的所有节点。二叉树的前序遍历、中序遍历、后序遍历都有递归和循环两种不同的实现方法。每种遍历的递归实现都比循环实现要简洁很多。下面分享一个关于二叉树遍历到笔试题:

  给定一棵完全二叉树,即树中的每一个节点有2个子节点或者没有子节点,每一个节点的值小于等于它的子节点的值。请找出该树中第二小的值。如果没有第二小的值,请给出-1;

  解题思路:画图举例解决问题,如下图所示,根节点是1,每一个节点的值小于等于它的子节点的值,访问根节点后再先后访问左子树和右子树,最后直到找到大于根节点的最小值;如果没有第二小的值,给出-1。   很明显,根据题意在遍历二叉树时采用前序递归遍历,得到的根节点和当前的第二小值比较,如果该值大于根节点(第一小的值)且小于第二最小值,则赋值给第二最小值。   另外,分析二叉树的结构可以做剪枝处理,因为每一个节点的值小于等于它的子节点的值,所以当该节点的值大于第二最小值时,其子节点肯定大于第二最小值,无需再遍历,可以减少遍历的运算量。

int findSecondMinimumValue(struct BSTreeNode *root)
{
    if (root == nullptr)
        return -1;
    int firstMin = root->m_nValue;   //第一小初始化
    int secondMin = 0x7FFFFFFF;  //第二小初始化
    findSecondMinimumValueCore(root, firstMin, secondMin);
    if (secondMin == 0x7FFFFFFF)  //如果没有第二小的值,secondMin未赋值,给出-1
        return -1;
    return secondMin;
}

void findSecondMinimumValueCore(struct BSTreeNode *root,int firstMin,int& secondMin)
{
    // 前序遍历
    int value = root->m_nValue;
    if (firstMin<value && secondMin>value)
        secondMin = value;
    if (root->m_pLeft && root->m_pLeft->m_nValue<secondMin) 
        // 剪枝,因为每一个节点的值小于等于它的子节点的值,如果该节点大于等于secondMin的值,则无需遍历,需要做剪枝提高效率
        findSecondMinimumValueCore(root->m_pLeft, firstMin, secondMin);
    if(root->m_pRight && root->m_pRight->m_nValue<secondMin)
        findSecondMinimumValueCore(root->m_pRight, firstMin, secondMin);
}

  完整的C++源代码: https://github.com/wylloong/TinyPrograms/blob/master/Coding%20Interviews/FindSecondMinValue.cpp

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏bboysoul

1176: C语言实验题――数组逆序

描述:输入10个整数存入一维数组,再按逆序重新存放后再输出。 输入:输入包括一行。 10个以空格格开的整数 输出:逆序的10个整数,整数以空格格开 样例输...

594
来自专栏计算机视觉与深度学习基础

Leetcode 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 a...

3084
来自专栏猿人谷

二叉树的遍历——递归和非递归

二 叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是 递归定义...

1848
来自专栏计算机视觉与深度学习基础

Leetcode 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 a...

2065
来自专栏个人分享

JAVA源码走读(二)二分查找与Arrays类

对数组排序:通过sort方法,按升序。 比较数组:通过equals方法比较数组中元素值是否相等。 查找数组元素:通过binarySearch方法能对排序好的数组...

754
来自专栏WD学习记录

牛客网 二叉树中和为某一值的路径

输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在...

683
来自专栏海天一树

二叉树的分层遍历

给定一棵二叉树,要求从上到下从左到右分层输出该二叉树的节点值。 ? bitree.png 一、递归法 二叉树本身就带有递归属性,通常我们可以用递归方法解决。假设...

2647
来自专栏mathor

BFPRT算法

 首先将原数组分成5个一组,每组内进行排序,组间不排序,然后将每组的中位数取出再次进行上述操作,直到最后只能分成一组了,然后取出中位数,将这个中位数当作标尺进行...

582
来自专栏C/C++基础

二叉树构建,先序,中序,后序遍历(以及非递归实现),广度优先遍历

二叉树是一类简单而又重要的树形结构,在数据的排序、查找和遍历方面有着广泛的应用。由于其清晰的结构,简单的逻辑,广泛的应用和大量的指针操作,在面试过程屡见不鲜,快...

361
来自专栏desperate633

LintCode 线段树系列问题(线段树的构造,线段树的构造||,线段树的查询,线段树的查询II,线段树的修改)线段树的构造线段树的构造 II线段树的查询线段树查询 II线段树的修改

线段树是一棵二叉树,他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start和end都是整数,并按照如下的方式赋值:

673

扫描关注云+社区