0%

[Leetcode]230. Kth Smallest Element in a BST(C++)

题目描述

题目链接:230. Kth Smallest Element in a BST

例子

例子 1

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

例子 2

Input: root = [5,3,6,2,4,null,null,1], k = 3
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?

解题思路

由于二叉搜索树的前序遍历结构就是排序好的结果,我们只需要在前序遍历过程中最终当前是第几小的节点,发现符合要求节点时返回即可,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int kthSmallest(TreeNode* root, int k) { return dfs(root, k); }

private:
int dfs(TreeNode* root, int& k) {
if (root == nullptr) {
return 0;
}
int val = dfs(root->left, k);
if (k == 0) return val;
k--;
if (k == 0) return root->val;
return dfs(root->right, k);
}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(h) — 二叉树最大高度

GitHub 代码同步地址: 230.KthSmallestElementInABst.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions