文章目录
- 一、题目描述
- 示例 1
- 示例 2
- 二、代码
- 三、解题思路
一、题目描述
给定一个二叉搜索树的根节点 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 <= 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]
三、解题思路
本题实际上是对二叉搜索树进行类似于中序遍历的遍历,二叉树搜索树的节点大小始终满足:中间节点元素始终大于节点左侧的元素,中间节点元素始终小于右侧节点元素。按照这个规律,将二叉搜索树的节点按照升序的顺序挨个遍历,最后能得到一个已排好序的数组,然后输出对应的位置的第k个最小的元素即可。