• 最近公共祖先（朴素法、倍增法、（递归法））

    目录

    一、前言

    二、题一：二叉树的最近公共祖先

    1、上链接

    2、基本思路

    （1）朴素法

    （2）LCA倍增法。

    3、朴素法代码

    （1）C++（AC）

    （2）python（29/31，时间超限了但算法正确性是可以保证的）

    4、LCA倍增法

    （1）C++（不提交，因为不想补全力扣给的入口函数，但是能保证算法正确性）

    5、其他递归法

    三、题二：【模板】最近公共祖先（LCA）

    1、上链接

    2、基本思路

    3、倍增法代码

    （1）C++ （AC）

    （2）python（70分）

    一、前言

    又是一个复习的算法题目，下面直接看题吧。

    二、题一：二叉树的最近公共祖先

    1、上链接

    236. 二叉树的最近公共祖先 - 力扣（Leetcode）

    2、基本思路

    有两种方法可解。

    （1）朴素法

    假设给定两个节点p，q，那么我们应该找出两条路径并存起来，路径是从根节点到给定节点，怎么找呢？利用栈进行递归查找即可。

    （2）LCA倍增法。

    为什么倍增法可行，因为一个整型数永远可以化成一个二进制数（二进制转十进制）。

    3、朴素法代码

    （1）C++（AC）

    顺便也复习了一下怎么建树。

    1. #include
    2. #include
    3. #include
    4. #include
    5. using namespace std;
    6.  
    7. ///**
    8. // * Definition for a binary tree node.
    9. // */
    10. struct TreeNode {
    11.     int val;
    12.     TreeNode *left;
    13.     TreeNode *right;
    14.     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    15. };
    16.  
    17. class Solution {
    18. 	int* nums;
    19. public:
    20. 	Solution(){
    21. 		nums=new int[11];
    22. 		int n[]={3,5,1,6,2,0,8,-1,-1,7,4};
    23. 		for(int i=0;i<11;++i)
    24. 			nums[i]=n[i];
    25.  
    26. //		for(int i=0;i<11;++i)
    27. //			cout<
    28. //		cout<
    29. 	}
    30.  
    31. 	void display(TreeNode* node){
    32. 		if(node){
    33. 			display(node->left);
    34. 			cout<val<
    35. 			display(node->right);
    36. 		}
    37. 	}
    38.  
    39. 	TreeNode* createTree(int idx){
    40. 		if(idx>10)
    41. 			return NULL;
    42. 		//cout<
    43. 		int num=nums[idx];
    44. 		TreeNode* t;
    45. 		if(num==-1){
    46. 			t = NULL;
    47. 		}else{
    48. 			t=new TreeNode(num);
    49. 			t->left=createTree(2*idx+1);
    50. 			t->right=createTree(2*idx+2);
    51. 		}
    52. 		return t;
    53. 	}
    54.  
    55. 	void dfs_search(TreeNode* node,TreeNode* target,vector &stack,vector &path){
    56. 		if(node==NULL)
    57. 			return;
    58. 		stack.push_back(node);
    59. //        cout<val<
    60. 		if(node->val==target->val){
    61. //			path=stack;
    62. 			path.assign(stack.begin(),stack.end());
    63. 			return;
    64. 		}
    65. //        cout<<"2"<
    66. 		dfs_search(node->left,target,stack,path);
    67. 		dfs_search(node->right,target,stack,path);
    68. 		stack.pop_back();
    69. 	}
    70.  
    71. 	//朴素法  用时击败16.68%，内存击败7.59%
    72.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    73.         vector p_path;
    74.         vector q_path;
    75.         vector stack;
    76.  
    77.         dfs_search(root,p,stack,p_path);
    78.         stack.clear();
    79.         dfs_search(root,q,stack,q_path);
    80. //
    81. //        for(int i=0;i
    82. //            cout<val<<" ";
    83. //        cout<
    84. //        for(int i=0;i
    85. //            cout<val<<" ";
    86. //        cout<
    87.  
    88.         TreeNode* common;
    89.         int i=0;
    90.         while(isize() && isize()){
    91.         	if(p_path[i]==q_path[i]){
    92.         		common=p_path[i];
    93. 			}
    94. 			i++;
    95. 		}
    96. 		return common;
    97.     }
    98. };
    99.  
    100. int main(){
    101. 	Solution Tree;
    102. 	TreeNode* root=Tree.createTree(0);
    103. //	Tree.display(root);
    104. 	int p,q;
    105. 	cin>>p>>q;
    106. 	TreeNode* pp=new TreeNode(p);
    107. 	TreeNode* qq=new TreeNode(q);
    108.  
    109. 	TreeNode* ans=Tree.lowestCommonAncestor(root,pp,qq);
    110. 	cout<val<
    111.  
    112. 	return 0;
    113. }

    （2）python（29/31，时间超限了但算法正确性是可以保证的）

    1. import copy
    2.  
    3. class TreeNode():   # python 没有结构体，但可以用类实现相同效果
    4.     def __init__(self,val:int,left=None,right=None):
    5.         self.val=val
    6.         self.left=left
    7.         self.right=right
    8.  
    9. def Create_Tree(node,vals,idx):
    10.     if idx>10:
    11.         return node
    12.     if vals[idx]=='#':
    13.         node=None
    14.     else:
    15.         node=TreeNode(int(vals[idx]))
    16.         node.left=Create_Tree(node.left,vals,2*idx+1)  
    17.         node.right=Create_Tree(node.right,vals,2*idx+2)
    18.     return node
    19.  
    20. def display(root):
    21.     if root:
    22.         display(root.left)
    23.         print(root.val)
    24.         display(root.right)
    25.  
    26. class Solution:
    27.     def __init__(self):
    28.         self.p_path=[]
    29.         self.q_path=[]
    30.         self.stack=[]
    31.  
    32.     def dfs_search(self,node:'TreeNode',target:'TreeNode',flg):
    33.         if node==None:
    34.             return
    35.         self.stack.append(node)
    36.         if node.val == target.val:
    37.             if flg==0:
    38.                 self.p_path=copy.deepcopy(self.stack)
    39.             else:
    40.                 self.q_path=copy.deepcopy(self.stack)
    41.             return
    42.         self.dfs_search(node.left,target,flg)
    43.         self.dfs_search(node.right,target,flg)
    44.         self.stack.pop()
    45.     
    46.     def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    47.         self.dfs_search(root,p,0)
    48.         self.stack.clear()
    49.         self.dfs_search(root,q,1)
    50.  
    51.         common=TreeNode(None);
    52.         i=0
    53.         while i<len(self.p_path) and i<len(self.q_path):
    54.             if self.p_path[i].val==self.q_path[i].val:
    55.                 common=copy.deepcopy(self.p_path[i])
    56.             i+=1
    57.         return common
    58.  
    59.    
    60. if __name__=='__main__':
    61.     node=None
    62.     vals=list("3516208##74")
    63.     root=Create_Tree(node,vals,0)
    64. ##    display(root)
    65.     n1,n2=map(int,input().split())
    66.     p=TreeNode(n1)
    67.     q=TreeNode(n2)
    68.  
    69.     sol=Solution()
    70.     ans=sol.lowestCommonAncestor(root,p,q)
    71.     print(ans.val)
    72.     
    73.     
    74.

    4、LCA倍增法

    （1）C++（不提交，因为不想补全力扣给的入口函数，但是能保证算法正确性）

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. const int N=10010;
    7. int n,m,cnt=1;
    8. struct Edge{
    9. 	int to,w,next;
    10. }edge[N];
    11. int head[N],dep[N],fa[N][N];
    12.  
    13. void Add(int u,int v){
    14. 	edge[cnt].to=v;
    15. 	edge[cnt].next=head[u];
    16. //	edge[cnt].w=w;
    17. 	head[u]=cnt;
    18. //	cout<<"对于"<
    19. 	cnt++;
    20. }
    21.  
    22. //int k=0; 
    23. void dfs(int v,int father){  //填深度表和跳步表 
    24. 	dep[v]=dep[father]+1;
    25. 	fa[v][0]=father;
    26. 	for(int i=1;i<=19;++i)
    27. 		fa[v][i]=fa[fa[v][i-1]][i-1];
    28. 	
    29. 	for(int i=head[v];i;i=edge[i].next){
    30. 		int p=edge[i].to;
    31. //		cout<
    32. //		k++;
    33. 		if(p!=father)
    34. 			dfs(p,v);	
    35. 	}
    36. }
    37.  
    38. int lca(int x,int y){
    39. //	cout<
    40. 	if(dep[x]
    41. 		swap(x,y);
    42. 	for(int i=19;i>=0;i--)   //先跳到同一层 
    43. 		if(dep[fa[x][i]]>=dep[y]){
    44. 			x=fa[x][i];
    45. //			cout<<"* "<
    46. 		}
    47. 			
    48. //	cout<<"11"<
    49. 	if(x==y)
    50. 		return y;
    51. //	cout<<"22"<
    52. 	for(int i=19;i>=0;i--){  //再跳到lca的下一层 
    53. 		if(fa[x][i]!=fa[y][i]){
    54. 			x=fa[x][i],y=fa[y][i];
    55. 		}		
    56. 	}
    57. 	return fa[x][0];
    58. }
    59.  
    60.  
    61. struct TreeNode {
    62. 	int val;
    63. 	TreeNode *left;
    64. 	TreeNode *right;
    65. 	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    66. };
    67.  
    68. class Tree{
    69. public:
    70. 	int nums[11] = {3,5,1,6,2,9,8,-1,-1,7,4};  //因为样例中有一个节点的值为0，导致dep[0]被更改了，所以调试了很久，这个样例我把0换成了9 
    71. //	int nums[2]={1,2};
    72. 	TreeNode* createTree(int idx){
    73. 		if(idx>10)
    74. 			return NULL;
    75. 		TreeNode* t;
    76. 		if(nums[idx]==-1){
    77. 			t=NULL;
    78. 			return t;
    79. 		}else{
    80. 			t=new TreeNode(nums[idx]);
    81. 			t->left= createTree(2*idx+1);
    82. 			t->right=createTree(2*idx+2);
    83. 		}
    84. 		return t;
    85. 	}
    86. 	void display(TreeNode* node){
    87. 		if(node){
    88. 			display(node->left);
    89. 			cout<val<
    90. 			display(node->right);
    91. 		}
    92. 	}
    93. 	void add_edge(TreeNode* node){ //链式前向星加边，当然也可以根据数组下标加边，这里建树再加边的操作略显复杂 
    94. 		if(node->left!=NULL){
    95. 			Add(node->val,node->left->val);
    96. 			Add(node->left->val,node->val);
    97. 			add_edge(node->left);
    98. 		}
    99. 		if(node->right!=NULL){
    100. 			Add(node->val,node->right->val);
    101. 			Add(node->right->val,node->val);
    102. 			add_edge(node->right);
    103. 		}	
    104. 	}		
    105. };
    106.  
    107.  
    108. int main(){
    109. 	Tree* t=new Tree();
    110. 	TreeNode* root=t->createTree(0);
    111. //	t->display(root);
    112. 	t->add_edge(root);
    113. //	cout<val<
    114. //	cout<<"dep[0]: "<
    115. 	dfs(root->val,0);
    116. 	int x,y;
    117. 	cin>>x>>y;
    118. 	int ans=lca(x,y);
    119. 	cout<
    120. 	
    121. 	return 0;
    122. }

    5、其他递归法

    1. class Solution {
    2. public:
    3.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    4.         if(root == NULL)
    5.             return NULL;
    6.         if(root == p || root == q) 
    7.             return root;
    8.             
    9.         TreeNode* left =  lowestCommonAncestor(root->left, p, q);
    10.         TreeNode* right = lowestCommonAncestor(root->right, p, q);
    11.        
    12.         if(left == NULL)
    13.             return right;
    14.         if(right == NULL)
    15.             return left;      
    16.         if(left && right) // p和q在两侧
    17.             return root;
    18.         
    19.         return NULL; // 必须有返回值
    20.     }
    21. };

    三、题二：【模板】最近公共祖先（LCA）

    1、上链接

    P3379 【模板】最近公共祖先（LCA） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

    2、基本思路

    为倍增法量身定做的一道题，下面用链式前向星+倍增法搞定。

    3、倍增法代码

    （1）C++ （AC）

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. int n,m,s; //树的结点个数、询问次数、树根节点的序号 
    7. int x,y; //x和y之间有一条直接连接的边 
    8. int a,b; //表示询问a和b的最近公共祖先 
    9.  
    10. const int N=5000100;
    11. int cnt=1,head[N];
    12. struct Edge{
    13. 	int to,next;
    14. } e[N];
    15.  
    16. int dep[N],fa[N][22];
    17.  
    18. void Add(int x,int y){
    19. 	e[cnt].to=y;
    20. 	e[cnt].next=head[x];
    21. 	head[x]=cnt++;
    22. }
    23.  
    24. void dfs(int u,int father){  //填深度表和跳步表 
    25. 	dep[u]=dep[father]+1; 
    26. 	fa[u][0]=father;
    27. 	for(int i=1;i<=19;++i)
    28. 		fa[u][i]=fa[fa[u][i-1]][i-1];
    29. 	
    30. 	for(int i=head[u];i;i=e[i].next){
    31. 		int p=e[i].to;
    32. 		if(p!=father)
    33. 			dfs(p,u);
    34. 	}
    35. }
    36.  
    37. int lca(int x,int y){
    38. 	if(dep[x]
    39. 		swap(x,y);
    40. 	for(int i=19;i>=0;i--)    //跳到同一层 
    41. 		if(dep[fa[x][i]]>=dep[y])
    42. 			x=fa[x][i];
    43. 			
    44. 	if(x==y)
    45. 		return y;
    46. 	
    47. 	for(int i=19;i>=0;i--)
    48. 		if(fa[x][i]!=fa[y][i])
    49. 			x=fa[x][i],y=fa[y][i];
    50. 	
    51. 	return fa[x][0];
    52. 	
    53. }
    54.  
    55. int main(){
    56. 	cin>>n>>m>>s;
    57. 	for(int i=0;i-1;++i){
    58. 		cin>>x>>y;
    59. 		Add(x,y);
    60. 		Add(y,x);
    61. 	} 
    62. 	dfs(s,0);
    63. //	cout<
    64. 	for(int i=0;i
    65. 		cin>>a>>b;
    66. 		cout<<lca(a,b)<
    67. 	}
    68. 	return 0;
    69. }

    （2）python（70分）

    1. N=500010
    2. # 没办法，N=5000010会全部时间超限
    3. cnt=1
    4. head=[0]*N
    5. next=[0]*N
    6. to=[0]*N
    7.  
    8. dep=[0]*N
    9. fa=[[0]*20 for _ in range(N)]
    10.  
    11. def Add(a,b):
    12.     global cnt
    13.     to[cnt]=b
    14.     next[cnt]=head[a]
    15.     head[a]=cnt
    16.     cnt+=1
    17.  
    18. def dfs(u:int,father:int):   # 填深度表和跳步表
    19.     dep[u]=dep[father]+1
    20.     fa[u][0]=father
    21.     for i in range(1,20):
    22.         fa[u][i]=fa[fa[u][i-1]][i-1]
    23.  
    24.     i=head[u]
    25.     while i:
    26.         p=to[i]
    27.         if p!=father:
    28.             dfs(p,u)
    29.         i=next[i]
    30.     
    31. def lca(x,y)->int:
    32.     if dep[x]
    33.         x,y=y,x
    34.     for i in range(19,-1,-1):    # 先跳到同一层
    35.         if dep[fa[x][i]]>=dep[y]:
    36.             x=fa[x][i]
    37.     if x==y:
    38.         return y
    39.     for i in range(19,-1,-1):
    40.         if fa[x][i]!=fa[y][i]:
    41.             x,y=fa[x][i],fa[y][i]
    42.     return fa[x][0]
    43.  
    44. n,m,s=map(int,input().split())
    45. for i in range(n-1):
    46.     x,y=map(int,input().split())
    47.     Add(x,y)
    48.     Add(y,x)
    49. dfs(s,0)
    50. for i in range(m):
    51.     a,b=map(int,input().split())
    52.     print(lca(a,b))

    以上，最近公共祖先

    祝好

  • 相关阅读:
    SveletJs学习——事件
    (STM32)从零开始的RT-Thread之旅--SPI驱动ST7735(2)
    Vue脚手架④
    第七章 树与森林
    spring aop 初探
    8月25日计算机视觉理论学习笔记——FCN、DeepLab
    Java实现Excel数据导入数据库
    C++核心编程：P19-＞STL----常用算法(下)
    利用Proxifier配置多级代理
    springboot教室实验室预约系统在线视频点播系统毕业设计毕设作品开题报告开题答辩PPT
  • 原文地址：https://blog.csdn.net/m0_52711790/article/details/127928596