167 lines
3.8 KiB
C++
167 lines
3.8 KiB
C++
#include <iostream>
|
||
#include <vector>
|
||
#include <queue>
|
||
#include <unordered_map>
|
||
#include <algorithm>
|
||
|
||
using namespace std;
|
||
|
||
/*====================================================
|
||
= 二叉树节点定义 =
|
||
====================================================*/
|
||
struct TreeNode {
|
||
int val;
|
||
TreeNode* left;
|
||
TreeNode* right;
|
||
|
||
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
|
||
};
|
||
|
||
/*====================================================
|
||
= 方法一：使用 parent 指针 + BFS 求树的直径 =
|
||
= 思路：Tree -> 无向图 -> 两次 BFS =
|
||
====================================================*/
|
||
|
||
/*
|
||
建立 parent 映射 + 邻接表
|
||
把“只有 left/right 的树”变成“无向图”
|
||
*/
|
||
void buildGraph(
|
||
TreeNode* root,
|
||
TreeNode* parent,
|
||
unordered_map<TreeNode*, vector<TreeNode*>>& adj
|
||
) {
|
||
if (!root) return;
|
||
|
||
if (parent) {
|
||
adj[root].push_back(parent);
|
||
adj[parent].push_back(root);
|
||
}
|
||
|
||
buildGraph(root->left, root, adj);
|
||
buildGraph(root->right, root, adj);
|
||
}
|
||
|
||
/*
|
||
从 start 出发 BFS，返回：
|
||
- 距离最远的节点
|
||
- 以及对应的距离
|
||
*/
|
||
pair<TreeNode*, int> bfs(
|
||
TreeNode* start,
|
||
unordered_map<TreeNode*, vector<TreeNode*>>& adj
|
||
) {
|
||
queue<TreeNode*> q;
|
||
unordered_map<TreeNode*, int> dist;
|
||
|
||
q.push(start);
|
||
dist[start] = 0;
|
||
|
||
TreeNode* far = start;
|
||
|
||
while (!q.empty()) {
|
||
TreeNode* u = q.front();
|
||
q.pop();
|
||
far = u;
|
||
|
||
for (TreeNode* v : adj[u]) {
|
||
if (!dist.count(v)) {
|
||
dist[v] = dist[u] + 1;
|
||
q.push(v);
|
||
}
|
||
}
|
||
}
|
||
|
||
return {far, dist[far]};
|
||
}
|
||
|
||
/*
|
||
使用 parent 思路求直径
|
||
*/
|
||
int diameterWithParent(TreeNode* root) {
|
||
if (!root) return 0;
|
||
|
||
unordered_map<TreeNode*, vector<TreeNode*>> adj;
|
||
|
||
// 建图（隐式利用 parent）
|
||
buildGraph(root, nullptr, adj);
|
||
|
||
// 第一次 BFS：随便找一个最远点 A
|
||
auto [A, _] = bfs(root, adj);
|
||
|
||
// 第二次 BFS：从 A 出发，找到最远点 B
|
||
auto [B, diameter] = bfs(A, adj);
|
||
|
||
return diameter;
|
||
}
|
||
|
||
/*====================================================
|
||
= 方法二：不使用 parent，仅用高度（树形 DP） =
|
||
= 思路：一次 DFS，自底向上 =
|
||
====================================================*/
|
||
|
||
int diameterByHeight = 0;
|
||
|
||
/*
|
||
返回：
|
||
- 以当前节点为起点，向下的最大深度
|
||
*/
|
||
int depth(TreeNode* root) {
|
||
if (!root) return 0;
|
||
|
||
int L = depth(root->left);
|
||
int R = depth(root->right);
|
||
|
||
// 更新直径：经过当前节点的最长路径
|
||
diameterByHeight = max(diameterByHeight, L + R);
|
||
|
||
// 返回当前子树高度
|
||
return max(L, R) + 1;
|
||
}
|
||
|
||
/*
|
||
使用高度法求直径
|
||
*/
|
||
int diameterWithHeight(TreeNode* root) {
|
||
diameterByHeight = 0;
|
||
depth(root);
|
||
return diameterByHeight;
|
||
}
|
||
|
||
/*====================================================
|
||
= main =
|
||
====================================================*/
|
||
int main() {
|
||
ios::sync_with_stdio(false);
|
||
cin.tie(nullptr);
|
||
|
||
/*
|
||
示例二叉树
|
||
1
|
||
/ \
|
||
2 3
|
||
/ \
|
||
4 5
|
||
\
|
||
6
|
||
|
||
直径路径：4 - 2 - 1 - 3 - 5 - 6
|
||
直径长度：5（边数）
|
||
*/
|
||
|
||
TreeNode* root = new TreeNode(1);
|
||
root->left = new TreeNode(2);
|
||
root->right = new TreeNode(3);
|
||
root->left->left = new TreeNode(4);
|
||
root->right->right = new TreeNode(5);
|
||
root->right->right->right = new TreeNode(6);
|
||
|
||
cout << "Diameter (with parent / BFS): "
|
||
<< diameterWithParent(root) << '\n';
|
||
|
||
cout << "Diameter (by height / DFS): "
|
||
<< diameterWithHeight(root) << '\n';
|
||
|
||
return 0;
|
||
}
|