🔥小龙报：个人主页 🎬作者简介：C++研发，嵌入式，机器人方向学习者 ❄️个人专栏：《算法通关指南》 ✨ 永远相信美好的事情即将发生
文章目录
- 前言
- 一、美国血统 American Heritage
-
- 2.1题目
-
- 2.2 算法原理
- 2.3代码
- 二、 二叉树问题
-
- 3.1题目
-
- 3.2 算法原理
- 3.3代码
- 总结与每日励志
前言
本专栏聚焦算法题实战，系统讲解算法模块：以《c++编程》，《数据结构和算法》《基础算法》《算法实战》 等几个板块以题带点，讲解思路与代码实现，帮助大家快速提升代码能力ps:本章节题目分两部分，比较基础笔者只附上代码供大家参考，其他的笔者会附上自己的思考和讲解，希望和大家一起努力见证自己的算法成长
一、美国血统 American Heritage
2.1题目
链接： 美国血统 American Heritage 
2.2 算法原理
解法同《求先序序列》，先手动动模拟一下，然后找出「相同子问题」，「递归」求解。 步骤： （1）先处理左右子树 （2）找根节点 （3）划分左右子树
2.3代码
#include <iostream>
using namespace std;
string a, b;
void dfs(int l1, int r1, int l2, int r2)
{
//递归窗口
if (l1 > r1)
return;
//寻找中序遍历中根节点的位置
int p = l1;
while (a[p] != b[l2])
p++;
//递归处理左右子树
dfs(l1,p – 1,l2 + 1,l2 + p – l1); //左子树
dfs(p + 1,r1,l2 + p – l1 + 1,r2); //右子树
//根节点
cout << b[l2];
}
int main()
{
cin >> a >> b;
dfs(0,a.size() – 1,0,b.size() – 1);
return 0;
}
二、 二叉树问题
3.1题目
链接： 二叉树问题
3.2 算法原理
深度： 递归。 宽度： 宽搜。 最近公共祖先： 两点之间的距离：通过向上不断找父亲结点。第⼀个重叠的位置，就是两者的最近公共祖先。可以一边寻找，一边计算结果。
3.3代码
//二叉树问题
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 110;
vector<int> tree[N];
int fa[N]; //f[i]:i的父亲节点
int dest[N]; //dest[i]：x到i经历的节点个数
// 深度
int dfs(int u)
{
int ret = 0;
for (auto v : tree[u])
ret = max(ret, dfs(v));
return ret + 1;
}
// 宽度
int bfs()
{
queue<int> q;
q.push(1);
int ret = 0;
while (q.size())
{
int sz = q.size();
ret = max(ret, sz);
while (sz—)
{
auto x = q.front();
q.pop();
for (auto v : tree[x])
q.push(v);
}
}
return ret;
}
int main()
{
int n;
cin >> n;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
tree[u].push_back(v);
fa[v] = u;
}
//深度
cout << dfs(1) << endl;
//宽度
cout << bfs() << endl;
//距离
int x, y;
cin >> x >> y;
while (x != 1)
{
dest[fa[x]] = dest[x] + 1;
x = fa[x];
}
int len = 0;
while (y != 1 && dest[y] == 0)
{
y = fa[y];
len++;
}
cout << 2 * dest[y] + len << endl;
return 0;
}
总结与每日励志
✨本章通过两道经典二叉树算法题，带你巩固递归、深搜、宽搜等核心思想。从美国血统的遍历重建，到二叉树深度、宽度与公共祖先求解，每道题都在训练分治思维与代码实现能力。算法之路无捷径，坚持刷题、理清思路、动手实现，能力便会稳步提升。保持热爱，脚踏实地，每一行代码、每一次思考，都在为更强的自己铺路，永远相信美好的事情即将发生。
