爲什麼這個算法的空間複雜度是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。