二叉搜索树的第k大节点

可以通过中序遍历二叉搜索树，得到递增的节点序列，然后取第k个节点即为第k大节点。具体实现可以使用递归或迭代方式。

以下是递归实现的示例代码：

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        self.count = 0
        self.result = None
        def inorder(node):
            if not node:
                return
            inorder(node.right)  # 先遍历右子树
            self.count += 1
            if self.count == k:
                self.result = node.val
                return
            inorder(node.left)  # 再遍历左子树
        inorder(root)
        return self.result

时间复杂度为 $O(N)$，其中 $N$ 为二叉搜索树的节点数。

相关问题

设二叉搜索树以二叉链表形式存放设计算法，从大到小输出给定二叉搜索树中结点值不小于k的数据元素。

算法步骤如下：

1. 从根节点开始遍历二叉搜索树，如果当前节点的值不小于k，则将其入栈。

2. 如果当前节点的右子树不为空，则将右子树入栈。

3. 如果当前节点的左子树不为空，则将左子树作为当前节点继续遍历。

4. 重复步骤1-3，直到栈为空。

5. 依次从栈中弹出元素，输出其值，直到栈为空。

这样就可以从大到小输出给定二叉搜索树中结点值不小于k的数据元素了。

找出一颗二叉搜索树中第k小的结点

二叉搜索树（BST）是一种能够快速查找某个值的二叉树，其中左子树的值均小于根节点的值，右子树的值均大于根节点的值。因此，中序遍历BST可以得到一个升序的序列。

根据中序遍历序列的特点，可以通过中序遍历BST来找到第k小的节点。具体步骤如下：

1. 对BST进行中序遍历，得到升序的节点序列。
2. 返回序列中第k个节点即为第k小的节点。

代码实现：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        # 中序遍历BST
        def inorder(root):
            if not root:
                return []
            return inorder(root.left) + [root.val] + inorder(root.right)
        
        # 返回第k小的节点值
        return inorder(root)[k-1]

时间复杂度：$O(n)$，其中$n$为BST中节点的个数。最坏情况下，需要遍历所有节点才能得到第k小的节点。

空间复杂度：$O(n)$，需要使用一个数组来存储节点的值。