二叉树直径计算：高效算法与实现

二叉树的直径定义为任意两节点间的最长路径长度。解决此问题的关键在于识别最长路径可能经过的潜在节点，并通过高效的遍历策略计算路径长度。以下是专业级的解决方案：

算法设计

1. 问题分析：

   • 最长路径可能不经过根节点，必须遍历所有节点寻找最大值
   • 路径长度由边数决定，非节点数
   • 树的高度计算是子问题的重复结构

2. 核心思想：

   • 采用后序遍历（Post-order Traversal）计算子树高度
   • 对每个节点计算左右子树高度之和作为潜在直径
   • 使用闭包变量维护遍历过程中的最大直径值

3. 复杂度分析：

   • 时间复杂度：O(n)，每个节点访问一次
   • 空间复杂度：O(h)，递归栈深度（h为树的高度）

实现代码

function diameterOfBinaryTree(root) {
    let maxDiameter = 0;
    
    const calculateHeight = (node) => {
        if (!node) return 0;
        const leftHeight = calculateHeight(node.left);
        const rightHeight = calculateHeight(node.right);
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
        return Math.max(leftHeight, rightHeight) + 1;
    };
    
    calculateHeight(root);
    return maxDiameter;
}

关键点解析

1. 后序遍历策略：

   • 先处理子节点再处理父节点，确保计算父节点时子节点高度已就绪
   • 符合树形结构的自底向上计算特性

2. 高度计算优化：

   • 空节点高度为0
   • 叶子节点高度为1（通过Math.max(0,0)+1实现）
   • 节点高度定义为到最远叶子节点的边数

3. 直径更新时机：

   • 每个节点访问时立即计算左右子树高度之和
   • 全局变量实时追踪最大值，避免二次遍历

测试用例

// 示例1：
//       1
//      / \
//     2   3
//    / \     
//   4   5    
// 最长路径：4-2-5 (3条边)
console.log(diameterOfBinaryTree({
    val: 1,
    left: {
        val: 2,
        left: { val: 4 },
        right: { val: 5 }
    },
    right: { val: 3 }
})); // 输出3

// 示例2：
// 单节点树
console.log(diameterOfBinaryTree({ val: 1 })); // 输出0

// 示例3：
// 右斜树
// 1
//  \
//   2
//    \
//     3
console.log(diameterOfBinaryTree({
    val: 1,
    right: {
        val: 2,
        right: { val: 3 }
    }
})); // 输出2

工程化建议

1. 类型安全：

   • 在TypeScript中应定义TreeNode接口确保类型正确

   interface TreeNode {
       val: number;
       left: TreeNode | null;
       right: TreeNode | null;
   }
   

2. 边界处理：

   • 显式处理空树输入(root=null)
   • 添加防御性代码校验节点结构

3. 性能监控：

   • 添加DEBUG模式输出递归调用次数
   • 使用memoization优化重复计算（虽然本算法已最优）

该方案符合LeetCode 543题的标准解法，在工程实践中展现了递归算法的简洁性和计算过程的高效性，适用于各类二叉树结构。