为什么该算法的空间复杂性为O（1）

Question

大家好：我阅读了下面的算法，以在二进制搜索树中找到两个节点的最低祖先。

 /* 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）更有意义的吗？

感谢这里的任何解释！

Answer 1

尽管您可以说，该算法的递归实现需要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 必须添加以保持语义不变。）

Answer 2

该算法涉及尾部递归。在您的问题的背景下，呼叫者的堆栈框架可以由Callee重复使用。换句话说，所有函数调用的嵌套序列都将要做的就是像桶旅一样将结果传递。因此，实际上只需要一个堆栈框架。

有关更多阅读，请参阅 尾声 在维基百科。