在第 4.6.5 节中，我们学习了自底向上的递归汇总思想：二叉树的最长路径必然在某个最高节点处“拐弯”。递归函数只需向上汇报当前节点的单侧最大深度，在回溯时顺便计算以当前节点为最高拐弯点的左深度与右深度之和，即可在 $O(n)$ 时间内顺手更新出全局最大直径。

题目

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是树中任意两个节点之间最长路径的边数。这条路径可能穿过也可能不穿过根节点。

输入格式

• 一行以空格分隔的若干个 token，表示二叉树的层序遍历序列。

输出格式

• 输出一个整数，表示二叉树的直径长度（边数）。

💡 输入提示

使用流分词极简读取；仅在 token != "null" 时调用 std::stoi，防止异常崩溃：

std::vector<std::string> tokens;
std::string token;
while (std::cin >> token) tokens.push_back(token);

样例

样例输入 1

1 2 3 4 5

样例输出 1

3

样例输入 2

1 2 null 3 4 5 null null 6

样例输出 2

4

样例输入 3

1

样例输出 3

0

路径不经过根节点的典型结构

样例 2 树形：
         1
        /
       2          <-- 最大直径经过节点 2（边数 = 4），而不穿过根节点 1！
      / \
     3   4
    /     \
   5       6
最长路径为 5 -> 3 -> 2 -> 4 -> 6，经过 4 条边，直径为 4。

如何验证

先安装 Node.js、pnpm 和支持 C++17 的编译器。GNU Make 是首选入口，但不是强制依赖。

# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make score

Windows 没有安装 Make 时，在仓库根目录使用完全相同的评分内核：

pnpm lab:doctor -- labs/chapter-04/exercise/E-04-26-diameter-of-binary-tree
pnpm lab:run -- labs/chapter-04/exercise/E-04-26-diameter-of-binary-tree
pnpm lab:run -- labs/chapter-04/exercise/E-04-26-diameter-of-binary-tree --case 001-sample
pnpm lab:score -- labs/chapter-04/exercise/E-04-26-diameter-of-binary-tree

make run 在答案尚未全对时仍正常返回，避免 Make 把学习结果显示成工具故障；make score 是严格入口，只有 100 分才返回成功。标准输出参与判题，调试信息请写入标准错误。

题解

点击查看题解

核心思路

1. 穿过节点 $u$ 的最长路径长度（边数）= 左子树最大深度 + 右子树最大深度；
2. 但为了让父节点继续计算，递归函数 只能返回以当前节点为起点的单侧最大深度：max(leftDepth, rightDepth) + 1；
3. 在后序遍历的过程中，利用引用变量 maxDia 随时用 L + R 更新全局最大直径。

复杂度分析

• 时间复杂度：$O(n)$，每个节点访问一次。
• 空间复杂度：$O(h)$。

点击查看参考代码

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

struct TreeNode {
    int val = 0;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;

    TreeNode() = default;
    TreeNode(int x) : val(x) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

TreeNode* buildTree(const std::vector<std::string>& tokens) {
    if (tokens.empty() || tokens[0] == "null") return nullptr;
    TreeNode* root = new TreeNode(std::stoi(tokens[0]));
    std::queue<TreeNode*> q;
    q.push(root);
    size_t i = 1;
    while (!q.empty() && i < tokens.size()) {
        TreeNode* curr = q.front();
        q.pop();
        if (i < tokens.size()) {
            if (tokens[i] != "null") {
                curr->left = new TreeNode(std::stoi(tokens[i]));
                q.push(curr->left);
            }
            i++;
        }
        if (i < tokens.size()) {
            if (tokens[i] != "null") {
                curr->right = new TreeNode(std::stoi(tokens[i]));
                q.push(curr->right);
            }
            i++;
        }
    }
    return root;
}

void freeTree(TreeNode* root) {
    if (!root) return;
    freeTree(root->left);
    freeTree(root->right);
    delete root;
}

int maxDepth(TreeNode* root, int& maxDia) {
    if (!root) return 0;
    int L = maxDepth(root->left, maxDia);
    int R = maxDepth(root->right, maxDia);
    maxDia = std::max(maxDia, L + R);
    return std::max(L, R) + 1;
}

int diameterOfBinaryTree(TreeNode* root) {
    int maxDia = 0;
    maxDepth(root, maxDia);
    return maxDia;
}

int main() {
    std::vector<std::string> tokens;
    std::string token;
    while (std::cin >> token) {
        tokens.push_back(token);
    }
    TreeNode* root = buildTree(tokens);
    std::cout << diameterOfBinaryTree(root) << "\n";
    freeTree(root);
    return 0;
}