为什么这个算法的空间复杂度是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

该算法涉及尾递归。在你的问题的上下文中，调用者的堆栈帧可以被调用者重用。换句话说，函数调用的所有嵌套顺序都是将结果传递给bucket bucket。因此，实际上只需要一个堆栈帧。

欲了解更多信息，请参阅维基百科的Tail Call。