递归和在二叉树

Question

继计数器变量是2码： 1.查找二叉查找树的第k个最小整数：

void FindKthSmallest(struct TreeNode* root, int& k) 
{ 
    if (root == NULL) return; 
    if (k == 0) return; // k==0 means target node has been found 
    FindKthSmallest (root->left, k); 

    if (k > 0) // k==0 means target node has been found 
    { 
    k--; 
    if (k == 0) { // target node is current node 
    cout << root->data; 
    return; 
    } else { 
    FindKthSmallest (root->right, k); 
    } 
    } 
} 

查找节点的二进制树编号：

int Size (struct TreeNode* root) 
{ 
    if (root == NULL) return 0; 
    int l = Size (root->left); 
    int r = Size (root->right); 
    return (l+r+1); 
} 

我的问题： 在这两个代码，我会跟踪我访问节点的数量。为什么是它的代码1，需要通过引用传递一个参数来跟踪我访问节点的数量，而代码2不要求按引用传递任何变量？

Answer 1

第一个代码（1）寻找您的BST最小的节点。您从树的左侧向下搜索，因为在该位置会找到最小值的节点。您进行多项检查：

• root == null - 确定树是否为空。
• k == 0 - 零在这种情况下是最小的元素。你基于这棵树的任何原理做出这个假设。

然后，您递归遍历列表以查找树左侧的下一个最小值。你执行一个多检查，如果你k > 0递减ķ<-这就是为什么你需要通过参考，因为你正在改变由一个单独的函数，全局变量等给予一定的价值k传递如果k恰好是零，那么你必须找到最小值的节点，如果不是，则转到当前节点的右侧，然后继续该过程。这似乎是找到最小的节点非常武断的方式...

对于第二个代码（2）你只是在计算节点在你的树从根开始，计数每个后续节点（或左或右）递归直到找不到更多的节点。您返回的结果是左节点，右节点的总数。并且因为它之前没有被计数，所以根为+1。在这种情况下，不需要通过引用变量传递，尽管如果您选择这样做，您可能会实现一个引用变量。

这是否帮助？

Answer 2

按引用传递参数允许你跟踪递归过程中计数的，否则计数将重置。它允许您修改内存空间中的数据，从而更改前一个值而不是当前/本地值。