题解 | 二叉搜索树中第K小的元素

题干分析

题设给定一颗二叉搜索树，要求我们找到所有节点中第k小的节点值。

算法思路

依照二叉搜索树的定义，其中序遍历结果即为所有节点值按从小到大排列得到的数组。得到该数组后返回其第k个元素即可。

实现代码

class Solution {
    void dfs(TreeNode *cur, vector<int> &order) {
        if (cur) {
            dfs(cur->left, order);
            order.push_back(cur->val);
            dfs(cur->right, order);
        }
    }
public:
    int kthSmallest(TreeNode* root, int k) {
        vector<int> order;
        dfs(root, order);
        return order[k - 1];
    }
};

复杂度分析

• 时间复杂度：每个节点都需要访问一次，时间复杂度为
• 空间复杂度：需要暂存中序遍历结果，空间复杂度为，递归最深为n层，空间复杂度仍为