一.题目要求

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

二.题目难度

中等

三.输入样例

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

四.解题思路

踩坑了 千万记得传引用别传值

五.代码实现

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {

        int target = 1;
        return mid(root, k, target);

    }

    int mid(TreeNode* node, int k,int &target) {
        if(!node) 
            return value;

        mid(node->left, k, target);

        if(k == target)
            value = node->val; 
        target++;

        mid(node->right, k, target);

        return value;
    }
private:
    int value = -1;
};

六.题目总结

在C++中，将变量作为参数传递给函数时，默认情况下是通过值传递（pass-by-value）。这意味着函数接收参数值的副本，对这个副本所做的任何更改都不会影响原始变量。
当你在mid函数中递归调用自身，并试图通过增加target的值来跟踪当前节点在中序遍历中的位置时，你实际上是在每次递归调用中更改target副本的值。一旦递归调用返回，这个更改就会丢失，因为它只影响了传递给该递归调用的target的副本，而不是所有递归调用中共享的一个target变量。
底层原理
当函数被调用时，其参数（如果是基本数据类型，如int、double等）会被复制到调用函数的栈帧（stack frame）中。栈帧是存储函数调用信息（如参数、局部变量和返回地址）的数据结构，每个函数调用都有自己的栈帧。因此，如果你在一个函数调用中修改了一个基本数据类型的参数，你只是修改了它在当前栈帧中的副本，原始变量（在调用函数的栈帧中）不会被更改。

解决方案
要解决这个问题，有几个选项：

• 使用引用传递（pass-by-reference）：通过将target作为引用传递给递归函数，你可以确保所有递归调用都操作同一个变量，而不是它的副本。这样，任何对target的更改都会保留下来。

int mid(TreeNode* node, int k, int& target) {
    // 函数体保持不变
}

• 返回并更新target：另一个选项是让mid函数返回当前的target值，并在每次递归调用后更新它。

int mid(TreeNode* node, int k, int target) {
    if(!node) 
        return target;

    target = mid(node->left, k, target);

    if(k == target)
        value = node->val; 
    target++;

    target = mid(node->right, k, target);

    return target;
}

使用类成员变量：虽然你已经尝试使用类成员变量value来存储结果，你也可以使用一个类成员变量来跟踪target的值。不过，这种方法可能需要更多的调整，以确保变量在每次kthSmallest函数调用之前被正确初始化。

通过以上任一解决方案，你可以确保target变量正确地跟踪中序遍历的进度，并且在递归过程中正确更新。