6

大家好：我阅读了下面的算法来找到二叉搜索树中两个节点的最低共同祖先。

 /* A binary tree node has data, pointer to left child
   and a pointer to right child */
 struct node
 {
  int data;
  struct node* left;
  struct node* right;
 };

 struct node* newNode(int );

/* Function to find least comman ancestor of n1 and n2 */
int leastCommanAncestor(struct node* root, int n1, int n2)
{
 /* If we have reached a leaf node then LCA doesn't exist
 If root->data is equal to any of the inputs then input is
 not valid. For example 20, 22 in the given figure */
 if(root == NULL || root->data == n1 || root->data == n2)
 return -1;

 /* If any of the input nodes is child of the current node
 we have reached the LCA. For example, in the above figure
 if we want to calculate LCA of 12 and 14, recursion should
 terminate when we reach 8*/
 if((root->right != NULL) &&
  (root->right->data == n1 || root->right->data == n2))
  return root->data;
 if((root->left != NULL) &&
 (root->left->data == n1 || root->left->data == n2))
 return root->data;   

 if(root->data > n1 && root->data < n2)
   return root->data;
 if(root->data > n1 && root->data > n2)
  return leastCommanAncestor(root->left, n1, n2);
 if(root->data < n1 && root->data < n2)
  return leastCommanAncestor(root->right, n1, n2);
}

请注意，上述函数假设 n1 小于 n2。时间复杂度：O(n)空间复杂度：O(1)

这个算法是递归的，我知道在调用递归函数调用时，函数参数和其他相关寄存器被压入堆栈，所以需要额外的空间，另一方面，递归深度与大小或高度有关树，比如说n，是O（n）更有意义吗？

感谢您在这里的任何解释！

4

2 回答 2

10

该算法涉及尾递归。在您的问题的上下文中，调用者的堆栈框架可以被被调用者重用。换句话说，所有嵌套的函数调用序列都会像桶旅一样将结果向上传递。因此，实际上只需要一个堆栈帧。

如需更多阅读，请参阅Wikipedia 上的Tail Call。

于 2010-10-20T15:24:50.813 回答
4

尽管您说该算法的递归实现由于需要堆栈空间而需要 O(n) 空间是正确的，但它仅使用尾递归，这意味着它可以重新实现以使用 O(1) 空间和循环：

int leastCommanAncestor(struct node* root, int n1, int n2)
    while (1)
    {
     /* If we have reached a leaf node then LCA doesn't exist
     If root->data is equal to any of the inputs then input is
     not valid. For example 20, 22 in the given figure */
     if(root == NULL || root->data == n1 || root->data == n2)
     return -1;

     /* If any of the input nodes is child of the current node
     we have reached the LCA. For example, in the above figure
     if we want to calculate LCA of 12 and 14, recursion should
     terminate when we reach 8*/
     if((root->right != NULL) &&
      (root->right->data == n1 || root->right->data == n2))
      return root->data;
     if((root->left != NULL) &&
     (root->left->data == n1 || root->left->data == n2))
     return root->data;   

     if(root->data > n1 && root->data < n2)
       return root->data;
     if(root->data > n1 && root->data > n2)
      root = root->left;
     else if(root->data < n1 && root->data < n2)
      root = root->right;
    }
}

（请注意，else必须添加以保持语义不变。）

于 2010-10-20T15:29:22.560 回答