Diameter of Binary Tree

543. 二叉树的直径

分析

主函数 diameterOfBinaryTree
- 初始化全局变量 res，用来存储最大直径
- 调用辅助函数 dfs，从根节点开始递归计算深度和路径长度
- 返回 res
辅助函数 dfs
- 基本情况：如果当前节点为空，返回深度为 0
- 递归计算左右子树深度：分别调用 dfs(root->left) 和 dfs(root->right)
- 更新直径：
  - 当前节点的路径长度为 left + right
  - 更新 res 为 max(res, left + right)
- 返回节点深度：节点的深度是其左右子树深度的最大值加 1

时间复杂度

时间复杂度 O(n)，其中 n 是节点总数，每个节点访问一次

空间复杂度

空间复杂度 O(h)，其中 h 是树的高度，递归栈的深度

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
public:
    int res = 0; // 保存树的最大直径

    int diameterOfBinaryTree(TreeNode* root)
    {
        // 调用辅助函数计算直径
        dfs(root);
        return res;
    }

    int dfs(TreeNode* root)
    {
        // 如果节点为空，返回深度为 0
        if (!root) return 0;

        // 递归计算左右子树的深度
        int left = dfs(root->left);
        int right = dfs(root->right);

        // 更新最大直径：当前节点的左子树深度 + 右子树深度
        res = std::max(res, left + right);

        // 返回当前节点的深度
        return std::max(left, right) + 1;
    }
};