在线编程介绍

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

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

题目描述

等级：容易
知识点：树

查看题目：35题：找出二叉搜索树的第2大的数 给定一个二叉搜索树，找出其第二大的数。
示例1
比如二叉搜索树如下

那么第二大的值是25
注意
对于二叉搜索树，若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值

解题思路

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

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

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