算法笔试模拟题精解之“找出二叉搜索树的第2大的数”-阿里云开发者社区

开发者社区> 被纵养的懒猫> 正文

算法笔试模拟题精解之“找出二叉搜索树的第2大的数”

简介: 这是一个关于二叉搜索树的知识点。对于二叉搜索树,若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值。
+关注继续查看

在线编程介绍

阿里云开发者社区在线编程产品,针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等,界面整洁明了,操作简单,为用户营造专心答题的学习环境。点击链接开始体验:https://developer.aliyun.com/coding

本文为大家介绍其中的第35题:找出二叉搜索树的第2大的数 的题目解析,具体如下:

题目描述

等级:容易
知识点:树

查看题目:35题:找出二叉搜索树的第2大的数 给定一个二叉搜索树,找出其第二大的数。
示例1
比如二叉搜索树如下
image.png
那么第二大的值是25
注意
对于二叉搜索树,若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值

解题思路

这是一个关于二叉搜索树的知识点。
对于二叉搜索树,若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值。
因为题中没有说这是一棵平衡的树,所以某些节点可能只有一棵子树。
对于树中最大的数是很容易找到的,一直选择右子树直到右子树为空就可以了。
对于第2大的数,存在两种情况。一种是最大数的节点存在左子树,一种是不存在左子树。

image.png

第一种情况下。根据二叉搜索树的性质,可以知道25的左子树中的所有值都比25小,也都比25的父节点(20)大。所以第二大的数应该出现在25的左子树中。寻找25左子树中的最大值即可。

image.png

第二种情况下。第二大的数就是最大数节点(60)的父节点(25).因为25的父节点和左子树都比25小。而右子树中只有最大数一个值。
对于特殊情况,根节点没有右子树。可以归类到情况1中,根节点为最大的树。如果也没有左子树的话,那就是样例有问题了,因为这样树中只有一个数。
时间复杂度O(n) 因为树不是平衡的,所以最差的情况下,从根节点开始都只有右子树,需要完整遍历整棵树。
空间复杂度O(1) 只需要保存当前遍历到的节点即可。
看完之后是不是有了想法了呢,快来练练手吧>>查看题目:找出二叉搜索树的第2大的数
image.png

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
《算法技术手册》一2.5 基准测试
本节书摘来华章计算机《算法技术手册》一书中的第2章 ,第2.5节, George T.Heineman Gary Pollice Stanley Selkow 著 杨晨 曹如进 译 译更多章节内容可以访问云栖社区“华章计算机”公众号查看。
860 0
粒子群优化算法(PSO)之基于离散化的特征选择(FS)(一)
欢迎大家关注我们的网站和系列教程:http://www.tensorflownews.com/,学习更多的机器学习、深度学习的知识! 作者:Geppetto 在机器学习中,离散化(Discretization)和特征选择(Feature Selection,FS)是预处理数据的重要技术,提高了算法在高维数据上的性能。
1132 0
LeetCode 700. 二叉搜索树中的搜索
给定二叉搜索树(BST)的根节点和一个值。
65 0
谷歌百度以图搜图 "感知哈希算法" C#简单实现
/// /// 感知哈希算法 /// public class ImageComparer { /// /// 获取图片的Hashcode /// /// /// public static string GetImageHashCode(string imageName) { int width = 8; int height = 8; // 第一步 // 将图片缩小到8x8的尺寸,总共64个像素。
1535 0
笔试算法模拟题精解之“完美排列”
本文通过两种解法描述86题“完美排列”的解题过程,更有对应的时间和空间复杂度帮助理解。
2051 0
人工智能: 自动寻路算法实现(一、广度优先搜索)
前言 随着人工智能技术的日益发达,我们的生活中也出现了越来越多的智能产品。我们今天要关注的是智能家居中的一员:扫地机器人。
1672 0
查找类算法之二分搜索树 | 算法必看系列十
二分搜索树是为了实现快速查找而生的,也支持快速添加和删除一个数据。如何查找某个元素首先跟根节点去做比较,如果相等的话就返回;如果待查元素要比根节点小,就进行左子树递归查找;如果待查元素要比根节点大,就进行右子树的递归查找;如果查找到最后还没有一个符合的元素,就返回null。
493 0
十大经典排序算法动画与解析,看我就够了!(配代码完全版) | 算法必看系列三十八
排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为 内部排序 和 外部排序 。内部排序是数据记录在内存中进行排序。而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
1385 0
560
文章
1795
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载