【算法通关指南：数据结构与算法篇】二叉树相关算法题：1.美国血统 American Heritage 2.二叉树问题

🔥小龙报：个人主页
🎬作者简介：C++研发，嵌入式，机器人方向学习者
❄️个人专栏：《算法通关指南》
✨ 永远相信美好的事情即将发生

文章目录

• 前言
• 一、美国血统 American Heritage
  • 1.1题目
    • 1.2 算法原理
    • 1.3代码
• 二、 二叉树问题
  • 2.1题目
    • 2.2 算法原理
    • 2.3代码
• 总结与每日励志

前言

本专栏聚焦算法题实战，系统讲解算法模块：以《c++编程》，《数据结构和算法》《基础算法》《算法实战》 等几个板块以题带点，讲解思路与代码实现，帮助大家快速提升代码能力ps:本章节题目分两部分，比较基础笔者只附上代码供大家参考，其他的笔者会附上自己的思考和讲解，希望和大家一起努力见证自己的算法成长

一、美国血统 American Heritage

1.1题目

链接：美国血统 American Heritage

1.2 算法原理

解法同《求先序序列》，先手动动模拟一下，然后找出「相同子问题」，「递归」求解。
步骤：
（1）先处理左右子树
（2）找根节点
（3）划分左右子树

1.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);return0;}

二、 二叉树问题

2.1题目

链接：二叉树问题

2.2 算法原理

深度： 递归。
宽度： 宽搜。
最近公共祖先： 两点之间的距离：通过向上不断找父亲结点。第⼀个重叠的位置，就是两者的最近公共祖先。可以一边寻找，一边计算结果。

2.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;return0;}

总结与每日励志

✨本章通过两道经典二叉树算法题，带你巩固递归、深搜、宽搜等核心思想。从美国血统的遍历重建，到二叉树深度、宽度与公共祖先求解，每道题都在训练分治思维与代码实现能力。算法之路无捷径，坚持刷题、理清思路、动手实现，能力便会稳步提升。保持热爱，脚踏实地，每一行代码、每一次思考，都在为更强的自己铺路，永远相信美好的事情即将发生。