我如何在递归调用之间保持状态

Question

这是我要解决的问题：在二叉搜索树中找到第 k 个最小的整数：

我的算法：我将对 BST 进行中序遍历。每访问一个节点，我都会将k减1，当k=0时，我应该在第k个最小的节点。

这是我的实现：

void FindKthSmallest(struct TreeNode* root, int k)
{
  if (root == NULL) return;
  if (k== 0) return;
  FindKthSmallest (root->left, k);
  k--;
  if (k == 0)
  {
    cout << root->data;
    return;
  }
  FindKthSmallest (root->right, k);
}

然而，通过上述实现，我发现无法在递归调用之间保持 k 的状态。

我认为 k 的状态需要在 2 种情况下保持：子与父之间的递归调用 returns 和父与子之间的递归调用 - 这就是我挣扎的地方。在这种情况下有没有办法保持状态？

Answer 1

在您的实现中，您使用变量 k 传递两条不同的信息：

找到目标节点前的剩余节点数
如果目标节点已经找到。

实际上只缺少 2 个。您可以通过以下方式实现：

i) 传递 k 作为参考而不是值。

ii) 通过 k 的值 0 分配上面 2.) 的含义。

结果将如下所示：

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);
    }
  }
}

另外请注意上面的实现是O(k)。使用 BST，您实际上可以在查找 k-th 最小整数时获得更好的性能。

我如何在递归调用之间保持状态

How can i maintain state between recursion calls

algorithm

tree

recursion

binary-tree

binary-search-tree