二叉树【北京大学】

牛客网题目链接 求一颗完全二叉树两个节点的最近公共祖先

题解

先把一个节点到根节点的路径存起来，然后计算另一个节点到根节点的路径，没到一个祖先节点查一下另一个节点是否存在，若存在则一定是最近公共祖先。

#include <iostream> #include <vector> #include <string> #include <cmath> #include <algorithm> #include <queue> #include <cstdio> #include <cctype> #include <unordered_map> #include <map> using namespace std; const int N = 105; typedef pair<int, string> PII; int main() { int a, b; while(cin>>a>>b){ unordered_map<int, bool> mp; while(a != 0){ mp[a] = true; a >>= 1; } int flag = 0; while(b != 0){ if(mp[b]) { cout<<b<<endl; break; } b >>= 1; } } return 0; }