35.找出二叉搜索树的第2大的数 - 图1

题目概述

题目详情(点我)

给定一个二叉搜索树，找出其第二大的数。
示例1
比如二叉搜索树如下
35.找出二叉搜索树的第2大的数 - 图2

那么第二大的值是25

注意
对于二叉搜索树，若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
（TreeNode的right，left，val这三个成员，分别表示左子节点，右子节点，节点值。）

输入:
二叉搜索树

输出:
第二大的数

题解

解题方法

  • 递归

算法知识

  • 树

    • 时间复杂度: n
    • 空间复杂度: 1

解题思路

审题

  • 给出一棵二叉搜索树

题目要求

  • 求第二大的值

思路

  • 右子树不存在，此时根节点为最大值

    • 则第二大的值在左子树, 因此只要获取左子树的最大值就好了
    • 若左子树的右子树为空, 则此时第二大值即为根节点的左子树的值
    • 若左子树的右子树不为空, 则第二大的值为左子树的右子树的右子树…直到右子树的右子树为空, 此时就获取到了最大值。

  • 若右子树存在, 以右子树的右子树为根节点递归下去, 直到右子树的右子树为空。

    1. 若此时右子树的左子树不为空, 则此时最大的值为右子树, 就必须以右子树的左子树为根节点, 不断往右走, 找到最大值。
    2. 若此时右子树的左子树为空, 则直接返回当前结点的值