Kth 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を入力すると、1ではなく2が返されます。 なぜ2つのコードが異なるのか分かりません。ご協力いただきありがとうございます！

Answer 1

int& k（参考）とint k（値）との間に大きな違いがあります。

最初のケースでは、k（たとえばk--）に加えられた変更は、パラメータとして渡された呼び出し関数の変数に反映されます。

2番目のケースでは、関数はkという独自のコピーを受け取り、それに加えられた変更は呼び出し関数に影響しません。

を参照番号（int &）としてkに変更することはできますが、これにより、電話を許可する方法が変更されます。あなたはおそらくまだヘルパー関数が必要ですが、すべてのコードをその中に入れることができます。