Skip to content

Latest commit

 

History

History
99 lines (71 loc) · 1.96 KB

0230-kth-smallest-element-in-a-bst.adoc

File metadata and controls

99 lines (71 loc) · 1.96 KB
Raw

230. Kth Smallest Element in a BST

{leetcode}/problems/kth-smallest-element-in-a-bst/[LeetCode - Kth Smallest Element in a BST^]

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

*Note: *

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

Example 1:

Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
Output: 3

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?

思路分析

二叉搜索树的中根遍历是排好序的，所以，求第 K 最小值，直接中根遍历即可。

树的非递归遍历还需要多加推敲，加强理解。

{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
一刷
link:{sourcedir}/_0230_KthSmallestElementInABst.java[role=include]
二刷
link:{sourcedir}/_0230_KthSmallestElementInABst_2.java[role=include]
三刷
link:{sourcedir}/_0230_KthSmallestElementInABst_3.java[role=include]