二叉树的直径：穿越树林的最长路径

生命的横跨：寻找树中的最大距离

想象你站在一片茂密的森林中，试图找出从一个极端到另一个极端最长能走多远。在二叉树的世界里，直径就是这样一种量度 —— 它不仅仅是一个数字，更是树的生命力和广度的见证。

直径的本质：不仅仅是长度

二叉树的直径（LeetCode第543题）是树中任意两个节点之间最长路径的长度。这个定义乍看可能简单，但蕴含着深刻的算法智慧。关键在于：

• 路径可以不经过根节点
• 长度定义为路径经过的边的数量
• 需要遍历整棵树才能找到最长路径

解题思路：寻径之旅的递归哲学

解决这个问题的核心是理解：树的直径 = 左子树深度 + 右子树深度

public class Solution {
    // 全局变量记录最大直径
    private int maxDiameter = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        // 计算深度的同时更新直径
        calculateDepth(root);
        
        // 返回边的数量，而非节点数
        return maxDiameter;
    }
    
    private int calculateDepth(TreeNode node) {
        // 递归终止条件：空节点深度为0
        if (node == null) return 0;
        
        // 递归计算左右子树深度
        int leftDepth = calculateDepth(node.left);
        int rightDepth = calculateDepth(node.right);
        
        // 更新最大直径
        // 当前节点的直径 = 左子树深度 + 右子树深度
        maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
        
        // 返回当前节点的最大深度
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

代码的深层逻辑解析

1. maxDiameter 全局变量

   • 记录树的最大直径
   • 在遍历过程中不断更新

2. calculateDepth() 方法

   • 同时完成两个任务： a. 计算节点深度 b. 更新最大直径

3. 直径计算的关键：leftDepth + rightDepth

   • 代表穿过当前节点的最长路径
   • 不一定经过根节点

迭代方法：显式深度遍历

public int diameterOfBinaryTree(TreeNode root) {
    if (root == null) return 0;
    
    int maxDiameter = 0;
    // 存储节点及其深度的栈
    Stack<TreeNode> nodeStack = new Stack<>();
    // 存储对应节点深度的栈
    Stack<Integer> depthStack = new Stack<>();
    
    nodeStack.push(root);
    depthStack.push(0);
    
    while (!nodeStack.isEmpty()) {
        TreeNode node = nodeStack.pop();
        int currentDepth = depthStack.pop();
        
        int leftDepth = node.left != null ? 
            getNodeDepth(node.left) : 0;
        int rightDepth = node.right != null ? 
            getNodeDepth(node.right) : 0;
        
        maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
        
        if (node.right != null) {
            nodeStack.push(node.right);
            depthStack.push(currentDepth + 1);
        }
        
        if (node.left != null) {
            nodeStack.push(node.left);
            depthStack.push(currentDepth + 1);
        }
    }
    
    return maxDiameter;
}

// 辅助方法：获取节点深度
private int getNodeDepth(TreeNode node) {
    if (node == null) return 0;
    return 1 + Math.max(
        getNodeDepth(node.left), 
        getNodeDepth(node.right)
    );
}

性能分析：算法的呼吸

时间复杂度：O(n)

• 每个节点仅访问常数次
• n为树中节点总数

空间复杂度：O(h)

• h为树的高度
• 最坏情况可达O(n)
• 最好情况（平衡树）为O(log n)

深度思考：直径背后的数学之美

1. 为什么深度和直径如此紧密相连？
2. 如何理解树的"横跨"概念？
3. 递归如何帮助我们解决复杂的遍历问题？

实际应用场景

• 网络拓扑分析
• 社交网络中的影响力研究
• 生物进化树的直径研究
• 组织结构的层级分析

递归的诗：寻径的艺术

二叉树直径不仅仅是一道算法题，更是递归思想的诗意展现。它教会我们：

• 复杂问题可以通过重复的简单逻辑解决
• 全局性质可以通过局部遍历逐步揭示
• 代码的优雅源于对问题本质的深刻理解

记住，探索二叉树的直径就像穿越知识的森林，重要的是保持好奇和系统的思考！

---

作者：忍者算法 公众号：忍者算法

我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～