求二叉树最近公共祖先LCA的brute-force算法

亦凉 2023-10-17 23:55 110阅读 0赞

#### 概念 ####

先来一张绝妙的百科配图  
![先来一张绝妙的百科配图][70]  
最近公共祖先(Lowest/Least Common Ancestor, LCA)

> 在图论和计算机科学领域，树或有向无环图（DAG）*T*中两个结点*p*、*q*的最近公共祖先是指这样一个具有最低高度（最大深度）结点：*p*和*q*为均该结点的子孙，这里我们定义每个结点都是自己的子孙（这样一来，如果从*q*可以直接向下追溯到*p*，那么*q*就是最近公共祖先）——[维基百科][Link 1]

Hmmm 浓浓的翻译腔  
这里我们只讨论一般二叉树的最近公共祖先问题

#### 算法思想 ####

这里我们只讨论一次遍历的brute-force算法，亦即对于每次询问，遍历所有结点，所以时间复杂度为O(n)  
（至于别的高效算法╮(╯▽╰)╭挖个坑学会了再填上）  
brute-force算法思路简单，代码写起来也不长，但时间复杂度决定了其不适用于多次询问的场景

递归算法思想：  
当遍历到结点ROOT时

1.  若ROOT为空节点，返回NULL
2.  若ROOT为p或q，则ROOT即LCA，返回ROOT
3.  若ROOT既不是p也不是q，递归左右子树
4.  若p、q分别位于ROOT的左右子树，ROOT为LCA
5.  若p、q均位于ROOT的左（右）子树，LCA在ROOT的左（右）子树中

非递归算法思想：  
利用非递归的后序遍历的特点

1.  查找p、q，当找到其中一个结点时，栈中包含该结点的所有祖先，将其栈中结点制到一个辅助栈中
2.  继续遍历直至找到另一个结点，此时我们就得到了p、q的祖先序列，分别存储在两个栈中
3.  从栈顶开始逐结点比较，第一个相同的结点即为LCA

#### 代码 ####

递归算法

BTNode* GetLCA(BTNode* ROOT, BTNode* p, BTNode *q)
    {
        
    	if (ROOT == NULL)
    		return NULL;
    	if (ROOT == p || ROOT == q)
    		return ROOT;
    	BTNode* left = GetLCA(ROOT->LLINK, p, q);
    	BTNode* right = GetLCA(ROOT->RLINK, p, q);
    	// p 和 q 不存在祖先关系
    	if (left != NULL && right != NULL)
    		return ROOT;
    	// p 和 q 其中一个是另一个的祖先
    	else if (left != NULL)
    		return left;
    	else if (right != NULL)
    		return right;
    	else
    		return NULL;
    		}

甚至我们可以写得更简洁一些

BTNode* GetLCA(BTNode* ROOT, BTNode* p, BTNode *q)
    {
        
    	if (ROOT == NULL || ROOT == p || ROOT == q)
    		return ROOT;
    	BTNode* left = GetLCA(ROOT->LLINK, p, q);
    	BTNode* right = GetLCA(ROOT->RLINK, p, q);
    	if (left != NULL && right != NULL)
    		return ROOT;
    	return left != NULL?left:right;
    }

非递归算法  
这种算法是来自王道19数据结构P136的修正

typedef struct{
        
    	BiTree t;
    	int tag;//0表示左子女已被访问，1表示右子女已被访问
    }stack;
    BTNode* GetLCA2(BTNode* ROOT, BTNode* p, BTNode *q)
    {
        
    	stack s[20], s1[20];//s[]存放先找到的元素及其祖先，s1存[]放后找到的元素及其祖先
    	int top = 0, top1 = 0, i, j, gotp = 0, gotq = 0; //已找到p、q时，gotp、gotq为1
    	BTNode *bt = ROOT;
    	while (bt != NULL || top > 0){
        
    		//while (bt != NULL&&bt != p&&bt != q){ //书中多了这层循环导致算法出错
    			while (bt != NULL){
         //若结点非空
    				s[++top].t = bt; //结点入栈
    				s[top].tag = 0;
    				bt = bt->LLINK; //沿左分支向下
    			}
    		//}
    		while (top != 0 && s[top].tag == 1){
         //若结点为空 且 栈不空 且 栈顶结点已访问过左右子女
    		//书中“不失一般”地假设先找到p，再找到q（我？？？），所以这里加入了对找到p、q先后次序的判断，
    		//以及对两种情况的分别处理
    			if (s[top].t == p&&top1==0){
         //若先找到p
    				for (i = 1; i <= top; i++) //将s的元素转入辅助栈s1保存
    					s1[i] = s[i];
    				top1 = top;
    				gotp = 1;
    			} //if
    			if (s[top].t == q&&top1 == 0){
         //若先找到q
    				for (i = 1; i <= top; i++) //将s的元素转入辅助栈s1保存
    					s1[i] = s[i];
    				top1 = top;
    				gotq = 1;
    			} //if
    			if (s[top].t == p&&gotq){
         //若后找到p
    				for (i = top; i > 0; i--){
         //将s的元素与s1的元素匹配
    					for (j = top1; j > 0; j--){
        
    						if (s1[j].t == s[i].t)
    							return s[i].t; //返回LCA
    					}
    				}
    			} //if
    			if (s[top].t == q&&gotp){
         //若后找到q
    				for (i = top; i > 0; i--){
         //将s的元素与s1的元素匹配
    					for (j = top1; j > 0; j--){
        
    						if (s1[j].t == s[i].t)
    							return s[i].t; //返回LCA
    					}
    				}
    			} //if
    			top--;
    		} //while
    		if (top != 0){
         //若结点为空 且 栈空或栈顶结点未访问右子女
    			s[top].tag = 1;
    			bt = s[top].t->RLINK; //沿右分支向下
    		}
    	} //while
    	return NULL; //无CA，即公共祖先
    }

但是我仍然觉得上面这种后序遍历之中的判断条件过于诡异，不是说不对，就是初次看时难以理解，不合我的思路，于是我改写成下面的

BTNode* GetLCA3(BTNode* ROOT, BTNode* p, BTNode *q)
    {
        
    	BTNode *bt = ROOT, *r = NULL, *s[20], *s1[20];//s[]存放先找到的元素及其祖先
    												  //s1存放后找到的元素及其祖先
    	int top = 0, top1 = 0, i, j, gotp = 0, gotq = 0; //已找到p、q时，gotp、gotq为1
    	while (bt != NULL || top > 0){
        
    		if (bt != NULL){
         //若结点非空
    			s[++top] = bt; //结点入栈
    			bt = bt->LLINK; //沿左分支向下
    		}
    		else{
         //若结点为空 且 栈不空
    			bt = s[top];
    			if (bt->RLINK&&bt->RLINK != r) //若结点为空 且 未访问右子女
    				bt = bt->RLINK; //沿右分支向下
    			else {
        
    				if (s[top] == p&&top1 == 0){
         //若先找到p
    					for (i = 0; i <= top; i++) //将s的元素转入辅助栈s1保存
    						s1[i] = s[i];
    					top1 = top;
    					gotp = 1;
    				} //if
    				if (s[top] == q&&top1 == 0){
         //若先找到q
    					for (i = 0; i <= top; i++) //将s的元素转入辅助栈s1保存
    						s1[i] = s[i];
    					top1 = top;
    					gotq = 1;
    				} //if
    				if (s[top] == p&&gotq){
         //若后找到p
    					for (i = top; i > 0; i--){
         //将s的元素与s1的元素匹配
    						for (j = top1; j > 0; j--){
        
    							if (s1[j] == s[i])
    								return s[i]; //返回LCA
    						}
    					}
    				} //if
    				if (s[top] == q&&gotp){
         //若后找到q
    					for (i = top; i > 0; i--){
         //将s的元素与s1的元素匹配
    						for (j = top1; j > 0; j--){
        
    							if (s1[j] == s[i])
    								return s[i]; //返回LCA
    						}
    					}
    				} //if
    				top--;
    				r = bt;
    				bt = NULL;
    			} //else
    		} //else
    	} //while
    	return NULL; //无CA，即公共祖先
    }

#### 结构体定义 ####

typedef struct BTNode
    {
        
    	char INFO;
    	struct BTNode *LLINK,*RLINK;
    }BTNode,*BiTree;

#### 头文件及主函数 ####

void main(){
        
    	BTNode *A = (BTNode*)malloc(sizeof(BTNode));
    	BTNode *B = (BTNode*)malloc(sizeof(BTNode));
    	BTNode *C = (BTNode*)malloc(sizeof(BTNode));
    	BTNode *D = (BTNode*)malloc(sizeof(BTNode));
    	BTNode *E = (BTNode*)malloc(sizeof(BTNode));
    	BTNode *F = (BTNode*)malloc(sizeof(BTNode));
    	BTNode *G = (BTNode*)malloc(sizeof(BTNode));
    	BTNode *H = (BTNode*)malloc(sizeof(BTNode));
    	BTNode *I = (BTNode*)malloc(sizeof(BTNode));
    	BTNode *p, *q, *ROOT, *res, *res2, *res3;
    	A->INFO = 'A';	A->LLINK = B;	A->RLINK = C;
    	B->INFO = 'B';	B->LLINK = D;	B->RLINK = E;
    	C->INFO = 'C';	C->LLINK = F;	C->RLINK = G;
    	D->INFO = 'D';	D->LLINK = H;	D->RLINK = I;
    	E->INFO = 'E';	E->LLINK = NULL;	E->RLINK = NULL;
    	F->INFO = 'F';	F->LLINK = NULL;	F->RLINK = NULL;
    	G->INFO = 'G';	G->LLINK = NULL;	G->RLINK = NULL;
    	H->INFO = 'H';	H->LLINK = NULL;	H->RLINK = NULL;
    	I->INFO = 'I';	I->LLINK = NULL;	I->RLINK = NULL;
    	ROOT = A;
    	p = E;
    	q = I;
    	res = GetLCA(ROOT, p, q);
    	res2 = GetLCA2(ROOT, p, q);
    	res3 = GetLCA3(ROOT, p, q);
    	printf("LCA of %c and %c is %c.\nLCA of %c and %c is %c.\nLCA of %c and %c is %c.\n", \
    	p->INFO, q->INFO, res->INFO, p->INFO, q->INFO, res2->INFO, p->INFO, q->INFO, res3->INFO);
    }

原来文章中出现了豹栗二字，文章在发表之前还要过审，口怕  
2019.05.29update：原来现在所有文章都要过审了

[70]: https://img-blog.csdn.net/20180829223013171?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MTA4OQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[Link 1]: https://en.wikipedia.org/wiki/Lowest_common_ancestor