二叉树的最近公共祖先

原创已于 2023-11-08 21:05:39 修改 · 粉丝可见 · 191 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/134105635

题目：

样例：

`cobol<br/>6 1 4<br/>2 5<br/>-1 -1<br/>1 4<br/>-1 -1<br/>-1 -1<br/>-1 3<br/>`

2

思路：

由题意，最近公共祖先就是，找出给出的两个结点的父结点是谁。

这里有两种情况

1、给定的两个结点都是孩子结点

2、给定的两个结点，一个是孩子结点，一个是父结点。

这里情况2 中给出的结点已经是父结点了，可以直接输出它的最近公共祖先就是该父结点。

又因为由于给出的是孩子，我们需要往上查找的，一般我们遍历二叉树都是从根节点往下遍历查找的。

这时候就涉及到了后序遍历，后序遍历就是左右中的遍历，即从孩子结点往根结点遍历。

这样就可以使得我们从孩子结点往根结点方向的向上遍历寻找最近公共祖先。

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
 
int n,node1,node2;// n为结点数量，node 为寻找的结点
 
umap<int,int>l,r;	// l 为左支树，r 为 右支树
 
int ansNode = 0;	// 答案最近公共祖先结点
 
int lowestCommonAncestor(int root,int &node1,int&node2)
{
	// 如果当前结点是空结点，那么返回空结点
	if(root == -1) return root;
	// 包含情况2 如果刚好给出的node结点是 公共祖先结点，那么我们返回公共祖先结点
	if(root == node1 || root == node2) return root;
	
	// 开始后序遍历
	int left = lowestCommonAncestor(l[root],node1,node2);
	int right = lowestCommonAncestor(r[root],node1,node2);
	
	// 如果当前结点的左右孩子结点都是有效的，返回当前结点判断是不是最近公共祖先结点
	if(left != -1 && right != -1) return root;
	else
	
	// 如果出现 分叉点 我们返回有效的孩子结点
	if(left != -1 && right == -1) return left;
	else if(left == -1 && right != -1) return right;
	else return -1;	// 如果都没有，返回 -1
}
 
inline void solve()
{
	// 输入各个信息
	cin >> n >> node1 >> node2;
	
	for(int i = 0;i < n;++i)
	{
		cin >> l[i] >> r[i];
	}
	
	// 开始后序遍历查找公共祖先结点
	ansNode = lowestCommonAncestor(0,node1,node2);
	
	// 输出答案
	cout << ansNode << endl;
}
 
int main()
{
//	freopen("a.txt", "r", stdin);
	IOS;
	int _t = 1;
//	cin >> _t;
	while (_t--)
	{
		solve();
	}
 
	return 0;
}