Diameter of Binary Tree（二叉树的直径）

题目 / Problem

中文： 给定一棵二叉树的根节点 root，返回这棵树的直径长度。

二叉树的直径是树中任意两个节点之间最长路径的长度。这条路径可能经过根节点，也可能不经过根节点。

两个节点之间路径的长度使用它们之间的边数表示，而不是节点数。

English: Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

示例 / Examples

Example 1

二叉树直径示例 / Diameter of binary tree example

Input:  root = [1,2,3,4,5]
Output: 3

最长路径可以是 [4,2,1,3] 或 [5,2,1,3]。路径包含 4 个节点、3 条边，因此直径为 3。
The longest path can be [4,2,1,3] or [5,2,1,3]. It contains 4 nodes and 3 edges, so the diameter is 3.

Example 2

Input:  root = [1,2]
Output: 1

    1
   /
  2

节点 1 和 2 之间只有一条边，因此直径为 1。
There is one edge between nodes 1 and 2, so the diameter is 1.

约束 / Constraints

树中的节点数在 [1, 10⁴] 范围内。
The number of nodes in the tree is in the range [1, 10⁴].
-100 <= Node.val <= 100

关键观察 / Key Observation

对于任意节点 node，经过该节点的最长路径由两部分组成：
For any node node, the longest path passing through it consists of two parts:

从 node 向下延伸到左子树最深节点的路径。
The path from node down to the deepest node in its left subtree.
从 node 向下延伸到右子树最深节点的路径。
The path from node down to the deepest node in its right subtree.

如果左子树深度为 leftDepth，右子树深度为 rightDepth，那么经过当前节点的路径长度为：
If the left and right subtree depths are leftDepth and rightDepth, the path length through the current node is:

leftDepth + rightDepth

整棵树的直径就是所有节点对应路径长度中的最大值。
The tree's diameter is the maximum of this path length over all nodes.

解题思路：后序深度优先搜索 / Approach: Postorder DFS

计算当前节点的深度之前，必须先知道左右子树的深度，因此使用后序遍历：
The depths of both subtrees must be known before calculating the current node's depth, so use postorder traversal:

递归计算左子树深度 leftDepth。
Recursively calculate leftDepth.
递归计算右子树深度 rightDepth。
Recursively calculate rightDepth.
使用 leftDepth + rightDepth 更新全局最大直径。
Update the global maximum diameter with leftDepth + rightDepth.
向父节点返回当前子树的最大深度：Math.max(leftDepth, rightDepth) + 1。
Return the current subtree's maximum depth to its parent: Math.max(leftDepth, rightDepth) + 1.

深度函数返回以节点数计算的向下最长路径长度：空节点返回 0，叶子节点返回 1。这样 leftDepth + rightDepth 正好等于经过当前节点的边数。
The depth function measures a downward path in nodes: a null node returns 0, and a leaf returns 1. With this convention, leftDepth + rightDepth equals the number of edges in the path through the current node.

JavaScript 实现 / JavaScript Implementation

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *   this.val = val ?? 0;
 *   this.left = left ?? null;
 *   this.right = right ?? null;
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number}
 */
function diameterOfBinaryTree(root) {
  let diameter = 0;

  function getDepth(node) {
    if (node === null) {
      return 0;
    }

    const leftDepth = getDepth(node.left);
    const rightDepth = getDepth(node.right);

    diameter = Math.max(diameter, leftDepth + rightDepth);

    return Math.max(leftDepth, rightDepth) + 1;
  }

  getDepth(root);
  return diameter;
}

执行过程 / Walkthrough

以 root = [1,2,3,4,5] 为例，后序遍历从叶子节点开始向上计算：
For root = [1,2,3,4,5], postorder traversal calculates values upward from the leaves:

当前节点 / Node	`leftDepth`	`rightDepth`	经过节点的路径 / Path Through Node	返回深度 / Returned Depth	当前直径 / Diameter
`4`	0	0	0	1	0
`5`	0	0	0	1	0
`2`	1	1	2	2	2
`3`	0	0	0	1	2
`1`	2	1	3	3	3

在根节点 1 处，左子树深度为 2，右子树深度为 1，所以经过根节点的路径有 2 + 1 = 3 条边，最终返回 3。
At root node 1, the left subtree depth is 2 and the right subtree depth is 1, so the path through the root contains 2 + 1 = 3 edges. The final answer is 3.

为什么最长路径不一定经过根节点？ / Why Might the Diameter Skip the Root?

某棵子树内部可能包含比任何经过整棵树根节点的路径更长的路径。例如：
A subtree may contain a path longer than every path passing through the tree's root. For example:

最长路径 5 → 3 → 2 → 4 → 6 不经过根节点 1。
The longest path 5 → 3 → 2 → 4 → 6 does not pass through root node 1.

因此不能只计算根节点的 leftDepth + rightDepth。必须在访问每个节点时都更新最大直径。
Therefore, calculating leftDepth + rightDepth only at the root is insufficient. Update the maximum diameter at every node.

复杂度 / Complexity

设树中有 n 个节点，树高为 h。
Let the tree contain n nodes and have height h.

时间复杂度：O(n)，每个节点只访问一次。
Time: O(n), because every node is visited once.
空间复杂度：O(h)，空间由递归调用栈占用。
Space: O(h), for the recursion stack.
- 平衡二叉树中为 O(log n)。
  It is O(log n) for a balanced tree.
- 树退化为链表时，最坏为 O(n)。
  It is O(n) in the worst case for a skewed tree.

低效解法对比 / Inefficient Approach

一种直观做法是对每个节点分别调用高度函数，再计算 leftDepth + rightDepth。这种方法会重复遍历相同子树。
A straightforward solution calls a separate height function at every node and calculates leftDepth + rightDepth. This repeatedly traverses the same subtrees.

在退化二叉树中，它的时间复杂度可能达到 O(n²)。后序遍历在一次 DFS 中同时计算深度和直径，将时间复杂度优化为 O(n)。
For a skewed tree, that approach can take O(n²) time. Postorder traversal computes both depth and diameter during one DFS, reducing the time complexity to O(n).

易错点 / Common Pitfalls

直径使用边数表示，不是路径中的节点数。
The diameter is measured in edges, not nodes.
最长路径不一定经过根节点，必须在每个节点处更新答案。
The longest path may not pass through the root, so update the answer at every node.
深度函数应向父节点返回单边最大深度，不能返回 leftDepth + rightDepth。
The depth function must return the maximum one-sided depth to its parent, not leftDepth + rightDepth.
leftDepth + rightDepth 只用于更新经过当前节点的直径候选值。
Use leftDepth + rightDepth only to update the diameter candidate through the current node.
单节点树的直径为 0，因为其中没有边。
A single-node tree has diameter 0 because it contains no edges.
节点数量最多为 10⁴，极度倾斜的树可能使部分 JavaScript 环境的递归调用栈过深。
With up to 10⁴ nodes, a highly skewed tree may exceed the recursion limit in some JavaScript environments.

Diameter of Binary Tree