剑指offer之面试题50树中两个结点的最低公共祖先

r囧r小猫 2022-07-24 04:14 106阅读 0赞

**问题描述**：

设计一个算法，找出给定的任意两个结点的公共父结点。

**实现代码**如下：

**方法一**、用链表记录遍历的路径，而后比较两个链表。

#include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <limits.h>
    struct TreeNode{
    	int value;
    	struct TreeNode *left;
    	struct TreeNode *right;
    };
    typedef struct TreeNode Node;
    
    struct List{
    	Node *value;
    	struct List *next;
    };
    typedef struct List List;
    
    bool doFindCommonNode(Node *node,int num,List *listNum){
    	if(node==NULL)return false;
    	if(node->value==num){
    		return true;
    	}
    	bool rs =false;
    	List *temp =(List *)malloc(sizeof(List));
    	temp->value=node;
    	temp->next=listNum->next;
    	listNum->next=temp;
    	rs = doFindCommonNode(node->left,num,listNum);
    	if(!rs)
    		rs = doFindCommonNode(node->right,num,listNum);
    	if(!rs){
    		listNum->next=temp->next;
    		free(temp);
    	}
    	return rs;
    }
    
    Node *findCommonNode(Node *head,int num1,int num2){
    	Node *rs=NULL;
    	List *listNum1 =(List *)malloc(sizeof(List));
    	List *listNum2 =(List *)malloc(sizeof(List));
    	
    	listNum1->next=NULL;
    	listNum2->next=NULL;
    	bool b1,b2;
    	if(head!=NULL){
    		b1 = doFindCommonNode(head,num1,listNum1);
    		if(num1==num2){
    			if(listNum1->next==NULL)
    				return NULL;
    			else
    				return listNum1->next->value;
    		}
    		b2 = doFindCommonNode(head,num2,listNum2);
    		if(b1 && b2){
    			List *longlist=listNum1->next;
    			List *shortlist=listNum2->next;
    			List *head1=listNum1->next;
    			List *head2=listNum2->next;
    			int count1=0,count2=0;
    			
    			while(head1!=NULL){
    				count1++;
    				head1=head1->next;
    			}
    			
    			while(head2!=NULL){
    				count2++;
    				head2=head2->next;
    			}
    			
    			int dis=count1-count2;
    			if(count1<count2){
    				List *temp = longlist;
    				longlist=shortlist;
    				shortlist=temp;
    				dis=count2-count1;
    			}
    			
    			int i=0;
    			for(i=0;i<dis;i++)
    				longlist=longlist->next;
    			
    			while(shortlist!=NULL && longlist!=NULL && longlist->value!=shortlist->value){
    				longlist=longlist->next;
    				shortlist=shortlist->next;
    			}
    			if(longlist!=NULL && shortlist!=NULL){
    				rs=longlist->value;
    			}
    		}
    	}
    	return rs;
    }
    
    int main(int argc, char *argv[])
    {
    	Node *head=(Node *)malloc(sizeof(Node));
    	head->value=0;
    	head->right=NULL;
    	head->left=(Node *)malloc(sizeof(Node));
    	head->left->value=1;
    	head->left->left=(Node *)malloc(sizeof(Node));
    	head->left->left->value=2;
    	head->left->left->left=NULL;
    	head->left->left->right=NULL;
    	head->left->right=(Node *)malloc(sizeof(Node));
    	head->left->right->value=3;
    	head->left->right->left=NULL;
    	head->left->right->right=NULL;
    	int num1,num2;
    	scanf("%d %d",&num1,&num2);
    	Node *rs = findCommonNode(head,num1,num2);
    	if(rs!=NULL)
    		printf("the common node is :%d\n",rs->value);
    	else
    		printf("there is no comomn Node!\n");
    	return 0;
    }

**方法二**、直接判断两个结点是否在当前结点的左右两侧，如在，则该结点就是所求。否则继续遍历。

#include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <limits.h>
    struct TreeNode{
    	int value;
    	struct TreeNode *left;
    	struct TreeNode *right;
    };
    typedef struct TreeNode Node;
    
    bool isfind = false;
    
    bool doFindCommonNode(Node *node,Node **rs,int num1,int num2){
    	if(isfind || node==NULL)return false;
    	if(node->value==num1){
    		return true;
    	}
    	if(node->value==num2){
    		return true;
    	}
    	bool left = doFindCommonNode(node->left,rs,num1,num2);
    	bool right = doFindCommonNode(node->right,rs,num1,num2);
    	if(num1==num2 && (left==true || right==true)){
    		isfind=true;
    		*rs=node;
    		return true;
    	}
    	if(left==true && right==true){
    		isfind=true;
    		*rs=node;
    		return true;
    	}else if(left==true || right==true){
    		return true;
    	}else{
    		return false;
    	}
    }
    
    Node *findCommonNode(Node *head,int num1,int num2){
    	Node **rs =(Node **)malloc(sizeof(Node *));
    	*rs=NULL;
    	if(head!=NULL){
    		if(doFindCommonNode(head,rs,num1,num2) && isfind){
    			printf("find the Node!\n");
    		}else{
    			printf("there is no comomn Node!\n");
    		}
    	}
    	return *rs;
    }
    
    int main(int argc, char *argv[])
    {
    	Node *head=(Node *)malloc(sizeof(Node));
    	head->value=0;
    	head->right=NULL;
    	head->left=(Node *)malloc(sizeof(Node));
    	head->left->value=1;
    	head->left->left=(Node *)malloc(sizeof(Node));
    	head->left->left->value=2;
    	head->left->left->left=NULL;
    	head->left->left->right=NULL;
    	head->left->right=(Node *)malloc(sizeof(Node));
    	head->left->right->value=3;
    	head->left->right->left=NULL;
    	head->left->right->right=NULL;
    	int num1,num2;
    	scanf("%d %d",&num1,&num2);
    	Node *rs = findCommonNode(head,num1,num2);
    	if(rs!=NULL)
    		printf("the common node is :%d\n",rs->value);
    	return 0;
    }

**参考资料**：  
剑指offer  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51386597  
作者：WSYW126