题意概括

给定一棵二叉树，计算它的直径长度。一棵二叉树的直径被定义为树中任意两个结点之间路径长度的最大值。路径长度以它们之间边的数目表示。这条路径可能穿过也可能不穿过根结点。

输入格式: 输入为层序遍历序列，包含整数或字符串 "null"。

数据范围:

• 节点值的范围是 $[-100, 100]$。
• 树中至少有一个非空节点。

基础知识

这个问题的解法与“二叉树中的最大路径和”非常相似，核心思想仍然是 深度优先搜索 (DFS) 和 后序遍历。

对于树中的任意一个节点 u，最长的路径（直径）有以下两种可能：

1. 路径穿过节点 u：这条路径的长度等于 u 的左子树深度 + u 的右子树深度。这里的“深度”指的是从子树根节点到最远叶子节点的边数。
2. 路径不穿过节点 u：这意味着最长路径完全包含在 u 的左子树或右子树内部。

一个直接的想法是递归地计算这三种情况的最大值，但这会导致重复计算，时间复杂度较高。

更高效的 $O(N)$ 做法是设计一个递归函数，例如 dfs(u)，让它在一次遍历中完成两件事：

1. 返回子树深度：函数 dfs(u) 返回以 u 为根的子树的深度（即从 u 出发到其最远叶子节点所经过的边数）。这个返回值将提供给 u 的父节点使用。
2. 更新全局直径：在计算深度的过程中，对于每个节点 u，我们都可以计算出穿过它的路径长度，即 左子树深度 + 右子树深度。我们用这个值来更新一个全局的直径变量 ans`。

具体的递归逻辑如下：

• dfs(u) 的功能：
  • 基本情况：如果 u 是空节点，其深度为 -1（这样叶子节点的深度 1 + max(-1, -1) 就正确地为 0）。
  • 递归：分别递归调用 l = dfs(u->left) 和 r = dfs(u->right) 获取左右子树的深度。
  • 更新直径：穿过 u 的路径有 l + 1 条边（左侧）和 r + 1 条边（右侧），总长为 l + r + 2。我们用 ans = max(ans, l + r + 2) 来更新全局最大直径。
  • 返回值：u 的深度是其左右子树深度的较大者加一，即 return 1 + max(l, r)。

由于输入是层序遍历字符串，我们需要先用队列辅助，将该序列解析并构建成一棵二叉树。

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

// 定义节点结构体
struct Nde {
    int v;
    Nde *l, *r;
    Nde(int val) : v(val), l(nullptr), r(nullptr) {}
};

int ans;

// dfs返回以u为根的子树深度(边数)，并更新全局直径ans
int dfs(Nde* u) {
    if (!u) {
        return -1; // 空节点的深度为-1
    }

    int ldep = dfs(u->l);
    int rdep = dfs(u->r);

    // 以当前节点u为“拐点”的路径长度为 ldep + rdep + 2
    ans = max(ans, ldep + rdep + 2);

    // 返回当前节点的深度
    return 1 + max(ldep, rdep);
}

void run() {
    int n;
    cin >> n;
    // cin会读取n，但不会消耗换行符，需要忽略掉
    cin.ignore(); 
    
    string line;
    getline(cin, line);
    stringstream ss(line);
    
    string val;
    vector<string> vals;
    while (ss >> val) {
        vals.push_back(val);
    }
    
    if (vals.empty() || vals[0] == "null") {
        cout << 0 << endl;
        return;
    }

    // 使用队列通过层序遍历结果建树
    Nde* root = new Nde(stoi(vals[0]));
    queue<Nde*> q;
    q.push(root);

    int i = 1;
    while (!q.empty() && i < vals.size()) {
        Nde* cur = q.front();
        q.pop();

        // 处理左孩子
        if (i < vals.size() && vals[i] != "null") {
            cur->l = new Nde(stoi(vals[i]));
            q.push(cur->l);
        }
        i++;

        // 处理右孩子
        if (i < vals.size() && vals[i] != "null") {
            cur->r = new Nde(stoi(vals[i]));
            q.push(cur->r);
        }
        i++;
    }

    ans = 0;
    dfs(root);
    cout << ans << endl;
}

int main() {
    // 关闭同步流
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    run();

    return 0;
}

/*
样例 1:
输入:
5
1 2 3 4 5
输出:
3

样例 2:
输入:
8
1 2 null 4 5 null null 6
输出:
4
*/