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

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

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

相关文章

来自专栏ml

hdu---(3779)Railroad(记忆化搜索/dfs)

Railroad Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (...

3355
来自专栏机器学习入门

LWC 63: 750. Number Of Corner Rectangles

LWC 63: 750. Number Of Corner Rectangles 传送门:750. Number Of Corner Rectangles Pr...

2107
来自专栏ml

POJ--Strange Way to Express Integers

Strange Way to Express Integers Time Limit: 1000MS Memory Limit: 131072K ...

2657
来自专栏null的专栏

挑战数据结构与算法面试题——80题全解析(一)

题目来源“数据结构与算法面试题80道”。这是第一部分,包含其中的第1题到第5题。 在此给出我的解法,如你有更好的解法,欢迎留言。 ? 问题分析:二叉查...

3245
来自专栏web前端-

css3渐变

线性渐变: 属性:linear-gradinet(开始位置 角度,起始颜色,终止颜色 ) 开始位置:渐变开始的位置,属性值可以为百分比/长度/left、righ...

672
来自专栏ml

uva----11729 Commando war (突击战争)

G Commando War Input: Standard Input Output: Standard Output “Wa...

2767
来自专栏有趣的Python

12-玩转数据结构-AVL

我们之前实现的那个二叉树在最差情况下会退化成链表,在现有二分搜索树基础上添加一定的机制,使得二分搜索树可以维持平衡二叉树性质。AVL树就是一种经典的平衡二叉树。

952
来自专栏有趣的Python

算法与数据结构(二)附录:冒泡&插入&选择&希尔排序对比

冒泡排序 冒泡排序(Bubble Sort),是一种 计算机科学领域的较简单的 排序算法。 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误...

2604
来自专栏算法修养

ZOJ 80ers' Memory

80ers' Memory ---- Time Limit: 1 Second      Memory Limit: 32768 KB ---- I guess...

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

数据结构 单链表元素定位 PTA

由于这个很简单,他也貌似没要判断溢出,取巧突破 #include<stdio.h> #include<malloc.h> #include<stdlib.h> ...

1797

扫码关注云+社区