题目描述

题目链接：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