二叉树中的递归和计数器变量

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

通过引用传递参数允许您在递归过程中跟踪计数，否则计数将重置。它允许您修改内存 space 中的数据，从而更改以前的值而不是 current/local 值。

Answer 2

第一个代码 (1) 正在寻找 BST 中的最小节点。您从根向下搜索树的左侧，因为最小值的节点将在该位置找到。你做了几个检查：

root == null - 判断树是否为空。
k == 0 - 在这种情况下，零是最小的元素。你是根据这棵树的任何原则做出这个假设的。

然后你递归地遍历列表，在树的左边找到下一个最小的。您再执行一次检查，如果 k > 0 递减 k <- 这就是您需要通过引用传递的原因，因为您正在更改由单独的函数、全局变量给出的某个值 k等。如果 k 恰好为零，那么您找到了最小值的节点，如果不是，则转到当前节点的右侧，然后从那里继续该过程。这似乎是一种非常随意的查找最小节点的方法...

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

这有帮助吗？

二叉树中的递归和计数器变量

Recursion and a counter variable in a binary tree

recursion

binary-tree

binary-search-tree