文章目录

• • 1. 题目
  • • 1.1 示例
    • 1.2 说明
    • 1.3 限制
    • 1.4 进阶
  • 2. 解法一（递归中序遍历）
  • • 2.1 分析
    • 2.2 实现
    • 2.3 复杂度

1. 题目

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 1 1 开始计数）。

1.1 示例

• 示例 1 1 1 ：

  • 输入： root = [3, 1, 4, null, 2] ， k = 1
  • 输出： 1 1 1

• 示例 2 2 2 ：

  • 输入： root = [5, 3, 6, 2, 4, null, null, 1], k = 3
  • 输出： 3 3 3

1.2 说明

• 来源： 力扣（LeetCode）
• 链接： https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst

1.3 限制

• 树中的节点数为 n n n ；
• 1 ≤ k ≤ n ≤ 1 0 4 1 \le k \le n \le 10^4 1≤k≤n≤104 ；
• 0 ≤ N o d e . v a l ≤ 1 0 4 0 \le Node.val \le 10^4 0≤Node.val≤104 。

1.4 进阶

如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

2. 解法一（递归中序遍历）

2.1 分析

实际上，由于题目指出这里给定的是一棵二叉搜索树，而由【数据结构Python描述】二叉搜索树简介与使用二叉搜索树实现有序映射可知，二叉搜索树有一个特殊的性质，即其中序遍历的结果是一个有序的递增序列，利用此性质可以方便地给出如下递归解法：

2.2 实现

from typing import Optional, List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def _kth_smallest(self, root: Optional[TreeNode], tree: List[int]):
        if not root:
            return
        self._kth_smallest(root.left, tree)
        tree.append(root.val)
        self._kth_smallest(root.right, tree)

    def kth_smallest(self, root: Optional[TreeNode], k: int) -> Optional[int]:
        tree = []
        self._kth_smallest(root, tree)
        print(tree)
        return tree[k - 1]


def main():
    node6 = TreeNode(1)
    node5 = TreeNode(4)
    node4 = TreeNode(2, left=node6)
    node3 = TreeNode(6)
    node2 = TreeNode(3, left=node4, right=node5)
    node1 = TreeNode(5, left=node2, right=node3)
    root = node1
    sln = Solution()
    print(sln.kth_smallest(root, 3))  # 3


if __name__ == '__main__':
    main()

2.3 复杂度

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)