【数据结构】（二叉树）求二叉树中两个节点的最近公共祖先节点递归&&非递归

古城微笑少年丶 2021-11-09 12:54 336阅读 0赞

## 求二叉树中两个节点的最近公共祖先节点 ##

### **递归求解：** ###

> **算法思想:** 首先是递归的算法对于递归算法核心就是查找，即在递归的过程中不断查找要查找的结点找到该结点时，就将该结点向上返回，当一个结点为需要查找结点的最小公共祖先时就将该节点向上返回。具体的过程请看代码注释

--------------------

**递归代码需要对三张子问题进行分类讨论：**

1.  观看下图第一个子问题若根节点为C对于根节点为C的子树我们知道他查询不到所以应该返回NULL
2.  对于根节点为F的子树我们可知F的右孩子是我们想要查询而在F这颗子树里面我们只能找到一个所以我们要将我们找到的这个结点返回即返回M
3.  对于根结点为B的子树我们得到了左面查询到的D和右面查询到的M所以我们将B结点返回因为B就是D与M的最近祖先

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70]

//查找二叉树结点的公共父节点
    //递归方法求解
    BiTree* LowestCommonAncestorInBinaryTree (BiTree *Root,char p,char q){
         //真实传参应为(BiTree *Root,BiTree p,BiTree q）
    																		//这里只是为了测试
    	if(!Root)
    		return NULL;
    	//if(Root==p||Root==q) //真实代码
    	//	return Root;
    
    	if(Root->data==p||Root->data==q) //若子身结点是p,或者q。返回自身结点
    		return Root;
    
    	BiTree *left=LowestCommonAncestorInBinaryTree (Root->lchild,p,q); //在树的左方进行查找
    	BiTree *right=LowestCommonAncestorInBinaryTree (Root->rchild,p,q); //在树的右面就行查找
    
    	if(left!=NULL&&right!=NULL) //这里可以想象图中的B结点 从B的左面找到了 D所以left不空 从B的右面找到了M所以 right不空
    		return Root;			//将B结点向上返回
    	if(left==NULL&&right==NULL)	//上一层B返回后有 还会去A的右侧进行查找，看图可以知道A的右侧返回为NULl  
    		return NULL;
    	return left==NULL? right:left; //此时递归来到了最后一层代码因为 A的left不为空 所以最后的left 就是结果								
    }

### **非递归求解：** ###

> \*\*算法思想：\*\*对于非递归的代码，首先我想到了，这个问题其实和[求x结点的祖先][x]是一样的性质所以我只是在求x结点最先的前提下对代码进行了更改，就是将两个结点的祖先，全部求出来，然后总头到尾就行遍历，遇到第一个不相等的，那么这个的上一个就是最近的共同祖先.----我的代码可能有点复杂

这个代码看起来貌似很复杂单其实他的道理就是后序非递归遍历,可见后序非递归遍历确实很强大.这段代码,是后序非递归遍历演变而成的求x结点的祖先再次演变而来的 其实就是多加了几句判断而已

//非递归求解
    BiTree* LowestCommonAncestorInBinaryTree2(BiTree *Root,char p,char q){
        
    	if(!Root)
    		return NULL ;
    	if(Root->data==p||Root->data==q)
    		return Root;
    	BiTree *pre;
    	BiTree *sq[MaxSize];
    	BiTree *sp[MaxSize];
    	int tq=-1,tp=-1;
    	int flag_q=0;  //设置标志位来检查结点是否被找到
    	int flag_p=0;
    	while(tq!=-1||tp!=-1||Root){
        
    		while(Root){
        
    			if(flag_q==0)	 //当结点未被找到的时候进行压栈
    				sq[++tq]=Root;
    
    			if(flag_p==0)
    				sp[++tp]=Root;
    
    			Root=Root->lchild;
    		}
    		if(flag_q==0)	 //这里其实就是两个结点 p与q 肯定有一个回先被找到一个后被找到 在两个都没有找到的时候 他们栈内的元素是相同的
    			Root=sq[tq];
    		if(flag_p==0)
    			Root=sp[tp];
    		if(Root->rchild==NULL||Root->rchild==pre){
         // 若p结点为空或者p结点的右子树已经被访问过说明是第三次来到p应该进行退栈操作
    
    			if(flag_q==0)	//这里也是如果没有被找到才会出栈
    				tq--;
    
    			if(flag_p==0)
    				tp--;
    	
    			if(Root->data==q){
        	 //被找到了标志位设为1
    				flag_q=1;
    			}
    			if(Root->data==p){
        
    				flag_p=1;
    			}
    
    			if(flag_p==1 && flag_q==1)  //同时被找到了 那么久返回
    				break;
    
    			pre=Root;
    			Root=NULL; //这里为 NULL目的就是退到树的上一层也就是让栈顶元素出栈 又因为右子树已经被访问过了 
    		}else{
        	
    			Root=Root->rchild;
    		}
    	}
    
    
    
    	for(int i=-1,j=-1;i<=tq&&j<=tp;i++,j++) //返回公共祖先
    		if(sq[i+1]!=sp[j+1])
    			return sq[i];
    		
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70]: /images/20211109/8edeb30ae9e04300a15461febe1cd0ed.png
[x]: https://blog.csdn.net/qq_41934478/article/details/98121209