剑指offer2之二叉搜索树的第K大节点

题目(二叉搜索树的第 K 大节点)

题目：给定一棵二叉搜索树，请找出其中的第 K 大的节点。

算法思路

说到二叉搜索树，然后要求第 k 大的节点，即涉及到顺序问题，那么立即联想到二叉搜索树的中序遍历就是递增序列。因此只要对二叉搜索树进行中序遍历，记录中序序列中的第 K 个节点即可。算法可以有递归版和非递归版

算法实现

递归版

非递归版

复杂度

时间和空间复杂度均为 O(n)。

参考

[1] <<剑指offer2>>