问题

我已经思考了这么长时间，都快把我的大脑炸糊了。可能是因为我还不完全理解递归。

我不明白为什么当 k 的值在等于 0 后，它的值不会变成负数。相反，它会保持为 0，直到辅助函数退出。我尝试传入一个初始值为零的整数，并且在其值等于 k 之前不断地加。然而，这导致了同样的问题，一旦它等于 k，它就会保持这种状态。

有人能解释一下为什么这个值保持不变吗？

以下是代码部分：

```java
class Solution {
    public int kthSmallest(TreeNode t, int k) {
        TreeNode tempNode = new TreeNode();
        int iter = 0;
        getKValue(t, k, tempNode); 
        return tempNode.val;
    }
    
    private static void getKValue(TreeNode t, int k, TreeNode temp) {
        if(t == null) {
            return;
        }

        getKValue(t.left, k, temp);
        
        k = k - 1;
        System.out.println(k);
        if(k == 0) {
            temp.val = t.val;
            return;
        }
        getKValue(t.right, k, temp);
    }
}

例如，对于下面的树，期望的输出是 1。但是我得到的是 3，控制台打印了两次 0。

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

2
输出：1

<details>
<summary>英文:</summary>

I&#39;ve mulled over this for so long it&#39;s frying my brain. It&#39;s possibly I don&#39;t fully understand recursion yet.

I don&#39;t understand why the value of k, after it equals reaches 0, does not go into the negatives. Instead it remains 0 until the helper function exists. I tried passing in an integer with an initial value of zero and adding until its value equaled k. However, this resulted in the same problem where once it equaled k, it remained that way.

Can someone please explain why the value stays the same?

    class Solution {
            public int kthSmallest(TreeNode t, int k) {
              TreeNode tempNode = new TreeNode();
              int iter = 0;
              getKValue(t, k, tempNode); 
              return tempNode.val;
            }
            
            private static void getKValue(TreeNode t, int k, TreeNode temp) {
                if(t == null) {
                    return;
                }
            
        
                getKValue(t.left, k, temp);
                
                
                k = k - 1;
                System.out.println(k);
                if(k == 0) {
                    temp.val = t.val;
                    return;
                }
                getKValue(t.right, k, temp);
            
            }
        }

For example, for the tree below the expected output is 1. But I get 3 and the console prints 0 twice.

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

</details>


# 答案1
**得分**: 1

我认为问题出在你在每次递归调用中都传递了 `k`。你不应该这样做，因为这会导致每次递归调用都获得自己的 `k` 的副本。这意味着当你修改 `k` 时：

    k = k - 1;

堆栈中的其他调用并不知道 `k` 的更改。就其他调用而言，`k` 仍然是 1，因为它们各自有自己的副本。

要解决这个问题，你应该有一个共享的 `k`，所有递归调用都可以访问：

        static int sharedK; // 共享的！
        public int kthSmallest(TreeNode t, int k) {
          TreeNode tempNode = new TreeNode();
          sharedK = k; // 设置 sharedK
          getKValue(t, tempNode); 
          return tempNode.val;
        }
        
        private static void getKValue(TreeNode t, TreeNode temp) {
            if(t == null) {
                return;
            }

            getKValue(t.left, temp);
            
            sharedK--; // 注意这里的更改
            System.out.println(sharedK);
            if(sharedK == 0) {
                temp.val = t.val;
                return;
            }
            getKValue(t.right, temp);
        }

如果可以通过引用传递 `k`，也可以实现相同的效果，但不幸的是，在 Java 中无法进行引用传递。

<details>
<summary>英文:</summary>

I think the problem is because you are passing `k` across each recursive call. You shouldn&#39;t do that because that causes each recursive call to get their own _copy_ of `k`. This means that when you modify `k`:

    k = k - 1;

The other calls down the stack does not know about `k` changing. As far as the other calls are concerned, `k` is still 1, because they each have their own copy.

To fix this, you should have one _shared_ `k`, that all the recursive calls can access:

        static int sharedK; // shared!
        public int kthSmallest(TreeNode t, int k) {
          TreeNode tempNode = new TreeNode();
          sharedK = k; // setting the sharedK
          getKValue(t, tempNode); 
          return tempNode.val;
        }
        
        private static void getKValue(TreeNode t, TreeNode temp) {
            if(t == null) {
                return;
            }

            getKValue(t.left, temp);
            
            sharedK--; // note the change here
            System.out.println(sharedK);
            if(sharedK == 0) {
                temp.val = t.val;
                return;
            }
            getKValue(t.right, temp);
        }

The same thing could be achieved if `k` were passed by reference, but unfortunately you can&#39;t pass by reference in Java.

</details>



# 答案2
**得分**: 0

我认为这个问题需要您输出二叉搜索树的第K小元素。这里是使用O(N)内存空间的代码，其中N是二叉搜索树中节点的数量。首先，我们将使用中序遍历（递归）遍历二叉搜索树，并将节点保存在一个数组或向量中。二叉搜索树的中序遍历会按顺序给出节点。

```cpp
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};

vector<int> nodes;

void inorder(TreeNode *root) {
    if (root != NULL) {
        inorder(root->left);
        nodes.push_back(root->val);
        inorder(root->right);
    }
}

class Solution {
public:
    int getValue(TreeNode* root, int K) {
        nodes.clear();
        if (root != NULL) {
            inorder(root);
            return nodes[K - 1];
        }
        return -1;
    }
};

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};

vector<int> nodes;

void inorder(TreeNode *root) {
    if(root!=NULL)
    {
        inorder(root->left);
        nodes.push_back(root->val);
        inorder(root->right);
    }
}
class Solution {
public:
    int getValue(TreeNode* root,int K)
    {
        nodes.clear();
        if(root!=NULL)
        {
            inorder(root);
            return nodes[K-1];
        }
        return -1;
    }
};

</details>