力扣热题100_二叉树_230_二叉搜索树中第K小的元素

---

题目链接

230. 二叉搜索树中第K小的元素

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

示例 1：

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

示例 2：

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

解题思路

递归遍历

• 采用中序遍历，即以左-根-右的顺序进行遍历，这样可以得到一个单调递增的数组。
• 我们可以用数组res存放遍历结果，当len(res) == k时退出遍历

解题代码

class Solution:def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:res = []  #存放遍历结果def dfs(root):if not root:returndfs(root.left)if len(res) == k: #已经找到第k小元素returnres.append(root.val)dfs(root.right)dfs(root)return res[-1]