题目描述
题目链接: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?
解题思路
由于二叉搜索树的前序遍历结构就是排序好的结果,我们只需要在前序遍历过程中最终当前是第几小的节点,发现符合要求节点时返回即可,代码如下:
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