算法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

提示：
树中的节点数为 n 。
1 <= k <= n <= 104
0 <= Node.val <= 104

题解：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
# 中序遍历，就是从小到大开始遍历
class Solution:def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:ans = 0def dfs(node:Optional[TreeNode]) -> None:nonlocal k,ansif node is None or k==0:return # 遍历左子树dfs(node.left)k-=1if k==0:ans = node.val# 遍历右子树dfs(node.right)dfs(root)return ans

思路

由于中序遍历就是在从小到大遍历节点值，所以遍历到的第 k 个节点值就是答案。

在中序遍历，即「左-根-右」的过程中，每次递归完左子树，就把 k 减少 1，表示我们按照中序遍历访问到了一个节点。如果减一后 k 变成 0，那么答案就是当前节点的值，用一个外部变量 ans 记录。