題目：

給定一個二叉搜索樹的根節點 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 記錄。