题目大意：
最小公共区域
给你一些区域列表 regions，每个列表的第一个区域都包含这个列表内所有其他区域。
很自然地，如果区域 X 包含区域 Y，那么区域 X 比区域 Y 大。
给定两个区域 region1 和 region2，找到同时包含这两个区域的 最小 区域。
如果区域列表中 r1 包含 r2 和 r3，那么数据保证 r2 不会包含 r3。
数据同样保证最小公共区域一定存在。
示例1:
输入： regions = [["Earth","North America","South America"], ["North America","United States","Canada"], ["United States","New York","Boston"], ["Canada","Ontario","Quebec"], ["South America","Brazil"]], region1 = "Quebec", region2 = "New York" 输出："North America"
提示：
- 2 <= regions.length <= 10^4
- region1 != region2
- 所有字符串只包含英文字母和空格，且最多只有 20 个字母。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1257
解题思路分析：
本题可以理解成一棵树，每个列表的第一个区域为根节点，其余的为第一个区域的子节点，遍历完所有区域列表后，一颗完整的树也就描画出来了。我们定义一个Map来表示树的结构，key为节点名称（某个区域），value是当前节点的父节点。
构建好树形结构之后，我们需要找到2个节点的最小共通父节点，之前做过类似的题目，找共通父节点的思路并不难，简单来说，就是从当前2节点向最顶的父节点画线，由于是树形结构，因此，从子节点到最顶部的根节点一定只存在唯一的路线，路线上每一个节点都是当前节点的父节点。2个子节点就存在2条路线，这2条路线的相交点即是最小共通父节点。
解题时，我们可以不断记录从当前2节点向顶部移动时经过的每一个节点，当某个节点重复出现时，即是答案。
实现代码：
public String findSmallestRegion(List<List<String>> regions,
String region1, String region2) {
// 描画树形结构，key是当前节点，value为父节点
Map<String, String> map = new HashMap<>();
for(List<String> region:regions){
// 首元素为父节点
String first=region.get(0);
for(int i=1;i<region.size();i++){
// 当前列表中每个元素的父节点为列表首元素
map.put(region.get(i),first);
}
}
// 记录访问过的父节点
Set<String> set = new HashSet<>();
// 从两个子节点开始向最顶部移动，找到第一个相交点
while(region1!=null || region2!=null){
if(region1 != null){
// 如果已经访问过region1，这是一个相交点，直接返回
if(set.contains(region1)) return region1;
// 将当前节点加入列表
set.add(region1);
// 将当前节点更新为其父节点，继续向上移动
region1=map.get(region1);
}
if(region2 != null){
// 如果已经访问过region2，这是一个相交点，直接返回
if(set.contains(region2)) return region2;
// 将当前节点加入列表
set.add(region2);
// 将当前节点更新为其父节点，继续向上移动
region2=map.get(region2);
}
}
return null;
}本题解法运行时间为9ms。
Runtime: 9 ms, faster than 98.45% of Java online submissions forSmallest Common Region.
Memory Usage: 46.6 MB, less than 100.00% of Java online submissions for Smallest Common Region.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1257-smallest-common-region-解题思路分析/