543. 二叉树的直径 (Easy)
专题归类： 05-二叉树 LeetCode 链接： https://leetcode.cn/problems/diameter-of-binary-tree/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一棵二叉树的根节点，返回该树的 直径。
直径 是指树中任意两个节点之间最长路径上的 边数。这条路径可能经过也可能不经过根节点。
示例 1：
输入：root = [1,2,3,4,5]
输出：3
解释：最长路径是 4-2-1-3 或者 5-2-1-3，长度为 3（边数）。
示例 2：
输入：root = [1,2]
输出：1
提示：
- 树中节点数目范围在
[1, 10^4]内 -100 <= Node.val <= 100
题目详细分析
- 数据范围含义： 节点数最多 10000，递归深度可能达到 10000，Python 默认递归深度可能不够，但一般二叉树不会是链状到 10000 层。
- 输入输出特征： 输入根节点，输出整数（最大边数，不是节点数）。
- 边界条件： 只有 1 个节点时，直径为 0（没有边）。只有 2 个节点时，直径为 1。
- 核心约束： 路径可以不经过根节点，所以必须在每个节点处计算「左子树深度 + 右子树深度」，取全局最大值。
- 隐藏条件： 直径是边数不是节点数。如果题目说「路径长度 = 路径上节点数 - 1」，那就是边数。
小白版直白理解
就像在一棵大树上找两个最远的果子之间的距离。你从树根出发，左枝伸出去 3 层，右枝伸出去 2 层，那么经过树根的最长路径就是 3+2=5 段树枝（边）。但是！最远的两个果子可能不经过树根，可能在某个分叉的左右两支上——所以你要在每个分叉点都算一遍「左边深度+右边深度」，取最大值。
解题思路
思路一：后序遍历 + 全局变量（推荐）
核心思想： 每个节点的「直径贡献」= 左子树深度 + 右子树深度。在后序位置（已经知道了左右子树的深度）计算这个值，用全局变量更新最大值。
为什么用后序？ 因为要知道「经过当前节点的最长路径」，必须先知道左子树有多深、右子树有多深——这是典型的需要子树信息来计算的场景，必须用后序。前序/中序在进入节点时还不知道子树的深度。
def diameterOfBinaryTree(root):
max_d = 0 # 全局变量，记录当前找到的最大直径
def depth(node):
nonlocal max_d
if not node:
return 0
# 后序：先计算左右子树的深度
left_depth = depth(node.left)
right_depth = depth(node.right)
# 经过当前节点的直径 = 左深度 + 右深度
max_d = max(max_d, left_depth + right_depth)
# 返回当前节点的深度（供父节点使用）
return 1 + max(left_depth, right_depth)
depth(root)
return max_d思路二：转化为最大深度问题
本质上和思路一相同，但更强调「深度是基础，直径是副产品」的思维。定义一个函数 maxDepth，在计算深度的同时更新全局直径。
def diameterOfBinaryTree(root):
max_d = 0
def max_depth(node):
nonlocal max_d
if not node:
return 0
l = max_depth(node.left)
r = max_depth(node.right)
max_d = max(max_d, l + r) # 更新直径
return 1 + max(l, r)
max_depth(root)
return max_d易错点
- 直径不经过根节点： 初学者常犯的错误是只算
maxDepth(root.left) + maxDepth(root.right)。但最长路径可能在左子树的内部，不经过根节点。必须每个节点都检查。 - 返回值和全局变量的区别： 递归函数的返回值是「当前节点的深度（向上汇报用）」，而全局变量 max_d 是「当前发现的最大直径（最终答案）」。两者意义不同。
- 直径是边数不是节点数： 如果有 3 个节点在一条链上，边数是 2，节点数是 3。本题是边数。
- 全局变量的作用域： 在 Python 中需要用
nonlocal声明才能在嵌套函数中修改外部变量。
框架提炼
后序归并 + 全局变量模板： 当需要在遍历树的同时记录一个「全局最优解」时，用这个模式：
def tree_solution(root):
best = initial_value
def postorder(node):
nonlocal best
if not node:
return base_value
left = postorder(node.left)
right = postorder(node.right)
# 后序位置：用左右子树的结果更新全局最优
best = max(best, compute(node, left, right))
# 返回当前节点对上一层的贡献
return contribution(node, left, right)
postorder(root)
return best这个模板适用于：直径（543）、最大路径和（124）、二叉树的相机监控（968）等问题。
关联题目
- 104-二叉树的最大深度 — 深度计算是本题的基础，直径 = 左右深度之和的全局最大值。
- 124-二叉树中的最大路径和 — 完全相同的思维模式（后序+全局变量），区别在于本题是边数而 124 是节点值和，本题取和而 124 需要做负值截断。
- 236-二叉树的最近公共祖先 — 也是后序遍历的应用，从子树获取信息做出判断。