#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;
}