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

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

  给定一棵完全二叉树,即树中的每一个节点有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 条评论
登录 后参与评论

相关文章

来自专栏小灰灰

JDK容器学习之LinkedHashMap(二):迭代遍历的实现方式

LinkedHashMap 如何保障有序的遍历 前一篇《JDK容器学习之LinkedHashMap (一):底层存储结构分析》 中介绍了LinkedHashM...

3617
来自专栏LeetCode

LeetCode 46 & 47. Permutations I&II

Given a collection of distinct integers, return all possible permutations.

2930
来自专栏数据结构与算法

2010 求后序遍历

2010 求后序遍历 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 白银 Silver 题目描述 Description 输入一...

3286
来自专栏小樱的经验随笔

Vijos P1114 FBI树【DFS模拟,二叉树入门】

描述 我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。 FBI树是一种二叉树1,它的...

2859
来自专栏俞其荣的博客

HashMap内部原理解析HeaderHashMap 必知源码分析Java 1.8 中 HashMap 的不同Footer

28010
来自专栏来自地球男人的部落格

[LeetCode] 78. Subsets

【原题】 Given a set of distinct integers, nums, return all possible subsets. Not...

2769
来自专栏LeetCode

leetCode 77&39. Combinations & Combination Sum

Given two integers n and k, return all possible combinations of k numbers out of...

1240
来自专栏恰童鞋骚年

剑指Offer面试题:22.二叉搜索树的后序遍历序列

  在后序遍历得到的序列中,最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分:第一部分是左子树结点的值,它们都比根结点的值小;第二部分是右子树结点的...

902
来自专栏java一日一条

Java 容器&泛型(1):认识容器

容器是Java语言学习中重要的一部分。泥瓦匠我的感觉是刚开始挺难学的,但等你熟悉它,接触多了,也就“顺理成章”地知道了。Java的容器类主要由两个接口派生而出:...

1212
来自专栏武培轩的专栏

Java中Set集合是如何实现添加元素保证不重复的?

Java中Set集合是如何实现添加元素保证不重复的? Set集合是一个无序的不可以重复的集合。今天来看一下为什么不可以重复。 Set是一个接口,最常用的实现类就...

3997

扫码关注云+社区

领取腾讯云代金券