二叉树的直径

LeetCode 官方题目链接

1. 题目呈现

难度等级：🟢 简单
核心考察点：二叉树、深度优先搜索 (DFS)、递归

给你一棵二叉树的根节点，返回该树的 直径 。

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

注意：两节点之间的路径长度是以它们之间边的数目表示。

示例 1：

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

    1
   / \
  2   3
 / \
4   5

示例 2：

输入：root = [1,2]
输出：1

---

2. 解题思路拆解

直径 的定义是任意两点间的最长路径。 对于任意一个节点 node，经过它的最长路径长度为：左子树的最大深度 + 右子树的最大深度。

所以，我们可以遍历每一个节点，计算经过该节点的最长路径，并更新全局最大值。 为了效率，我们可以在计算 深度 (Height) 的过程中顺便计算 直径 (Diameter)。

1. 定义递归函数 depth(node)：

   • 返回以 node 为根的子树的最大深度（节点数）。
   • depth = max(leftDepth, rightDepth) + 1。

2. 更新全局最大直径 maxDiameter：

   • 在 depth 函数内部，每次算出左右子树深度后，计算 leftDepth + rightDepth。
   • maxDiameter = max(maxDiameter, leftDepth + rightDepth)。
   • 注意：深度通常指节点数（或者层数），而题目中的路径长度是边的数量。
   • 如果 leftDepth 和 rightDepth 返回的是高度（层数），那么经过当前节点的路径边数刚好是 leftDepth + rightDepth (假设空节点深度为0)。

---

3. 代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function(root) {
    let maxDiameter = 0;
    
    // 计算树的高度（深度），并同时更新直径
    const depth = (node) => {
        if (!node) return 0;
        
        const leftDepth = depth(node.left);
        const rightDepth = depth(node.right);
        
        // 经过当前节点的最长路径 = 左深度 + 右深度
        // 注意：这里的深度定义为“经过的节点数”，但边数 = L + R
        maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
        
        // 返回当前树的高度
        return Math.max(leftDepth, rightDepth) + 1;
    };
    
    depth(root);
    return maxDiameter;
};

代码执行演示

输入 root = [1, 2, 3, 4, 5]

1. depth(1)
   • depth(2)
     • depth(4) -> L=0, R=0. maxD=0. Returns 1.
     • depth(5) -> L=0, R=0. maxD=0. Returns 1.
     • Back at 2: leftDepth=1, rightDepth=1.
     • maxDiameter = max(0, 1+1) = 2.
     • Returns max(1,1) + 1 = 2.
   • depth(3) -> L=0, R=0. Returns 1.
   • Back at 1: leftDepth=2, rightDepth=1.
   • maxDiameter = max(2, 2+1) = 3.
   • Returns 3.

Result: 3.

---

4. 复杂度分析

维度	描述
时间复杂度	$O(n)$。每个节点访问一次。
空间复杂度	$O(h)$。递归栈深度。