剑指offer（java版）面试题54：二叉搜索树的第k个结点

74 阅读 0 评论 49 点赞

我是靠谱客的博主精明篮球，最近开发中收集的这篇文章主要介绍剑指offer（java版）面试题54：二叉搜索树的第k个结点，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / 3 7 / / 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。

思路：

感觉题目描述有歧义，应该说是从小到大排序后找出第k个节点。二叉搜索树的性质：左<中<右，因此可以使用中序遍历。找到第k个节点时，返回。

1.遍历左子树，如果左子树的节点个数>=k，要找的节点就在左子树中

2.如果左子树返回null，即左子树的个数<k，要找的节点在右子树中

3.使用变量count记录已访问的节点个数，到第k个节点时，返回该节点。

代码：

private int count;

public TreeNode KthNode(TreeNode node, int k) {
    if (node == null) {
        return null;
    }

    TreeNode left = KthNode(node.left, k);
    if (left != null) {
        return left;
    }

    if (++count == k) {
        return node;
    }

    return KthNode(node.right, k);
}