KST BST递归解决方案中的最小元素

Question

此代码返回BST中第k个最小元素。

/** 
* Definition for a binary tree node. 
* struct TreeNode { 
*  int val; 
*  TreeNode *left; 
*  TreeNode *right; 
*  TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
* }; 
*/ 
class Solution { 
public: 
int fid; 

void inorder(TreeNode* node, int& fid, int& k) { 
if (!node) return; 
inorder(node->left, fid, k); 
if (!k) return; 
fid = node->val; 
k--; 
inorder(node->right, fid, k); 
} 

int kthSmallest(TreeNode* root, int k) { 
inorder(root, fid, k); 
return fid; 
} 
}; 

它给出了正确的答案。 我想我可以通过将inorder函数和kthSmallest函数结合起来来简化代码。

class Solution { 
public: 
int fid; 
int kthSmallest(TreeNode* root, int k) { 
if (!root) return fid; 
kthSmallest(root->left, k); 
if (!k) return fid; 
fid = root->val; 
k--; 
kthSmallest(root->right, k); 
return fid; 
} 
}; 

它给出了错误的答案。如果我输入BST {2,1} k = 1，它将返回2而不是1. 我不明白为什么两个代码是不同的。谢谢你的帮助！

Answer 1

作为参数，int& k（通过引用）和int k（通过值）之间存在很大差异。

在第一种情况下，对k（如k--）所做的任何更改都反映在作为参数传递的调用函数的变量中。

在第二种情况下，函数接收到自己的副本k，并且对其进行的任何更改都不会影响调用函数。

您可以更改您的kthSmallest以k作为参考（int &），但这会改变您允许调用它的方式。你可能仍然需要一个辅助函数，但是你可以把所有的代码放进去。