LeetCode 230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?


Try to utilize the property of a BST.
What if you could modify the BST node’s structure?
The optimal runtime complexity is O(height of BST).


分析:二叉搜索树的中序遍历是从小到大排序的,将前k个遍历结果放入nums中,当nums.size() >= k的时候返回nums[k-1]~


❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版