二叉搜索树中第 k 小的元素

问题分析

给定一个二叉搜索树（BST）的层序表示和一个整数 k，要返回其中第 k 小的节点值。BST 的性质是：左子树所有节点值都小于根节点值，右子树所有节点值都大于根节点值。因此，对 BST 进行中序遍历（左→根→右）会得到一个升序序列，第 k 个访问到的节点就是答案。

解题思路

1. 构造二叉树

Leetcode 44.二叉搜索树中第K小的元素-原题链接

题目内容

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

输入描述

• 第一行有两个整数$n,k$，$n$是$root$的长度
• 第二行为二叉树的序列化数组$root$，节点值之间用空格隔开，空节点用null表示。

输出描述

输出第 $k$ 小的元素。

样例1

输入

5 1
3 1 4 null 2

输出

1

样例2

输入

8 3
5 3 6 2 4 null null 1

输出

3

提示

• 树中的节点数为 $n$ 。
• $1 <= k <= n <= 10^4$
• $0 <= Node.val <= 10^4$