找出该树中第二小的值--思路及算法实现
在二叉树中最重要的操作莫过于遍历，即按照某一顺序访问树中的所有节点。二叉树的前序遍历、中序遍历、后序遍历都有递归和循环两种不同的实现方法。每种遍历的递归实现都比循环实现要简洁很多。下面分享一个关于二叉树遍历到笔试题：
给定一棵完全二叉树，即树中的每一个节点有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
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-11-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读