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

---

一、题目描述

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

示例 1

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

示例 2

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

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

二、代码

代码如下：

# 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:
        nums = []
        def find(r):
            if r.left != None:
                find(r.left)
            nums.append(r.val)
            if r.right != None:
                find(r.right)
        find(root)
        print(nums)
        print(nums[k-1])
        return nums[k-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

三、解题思路

本题实际上是对二叉搜索树进行类似于中序遍历的遍历，二叉树搜索树的节点大小始终满足：中间节点元素始终大于节点左侧的元素，中间节点元素始终小于右侧节点元素。按照这个规律，将二叉搜索树的节点按照升序的顺序挨个遍历，最后能得到一个已排好序的数组，然后输出对应的位置的第k个最小的元素即可。