Java树直径详解（从零开始掌握二叉树最长路径算法）

解题思路

要计算树的最长路径Java实现，我们可以利用深度优先搜索（DFS）的思想：

• 对于每个节点，计算其左子树的最大深度和右子树的最大深度。
• 该节点作为“拐点”时，能形成的最长路径 = 左子树深度 + 右子树深度。
• 全局记录所有节点中最大的这个值，就是整棵树的直径。

Java代码实现

下面是一个完整的Java实现，包含注释帮助你理解每一步：

class TreeNode {    int val;    TreeNode left;    TreeNode right;        TreeNode(int x) {        val = x;    }}public class TreeDiameter {    private int diameter = 0; // 全局变量，记录最大直径        public int diameterOfBinaryTree(TreeNode root) {        if (root == null) return 0;        depth(root); // 触发DFS        return diameter;    }        // 返回当前节点的最大深度，并更新直径    private int depth(TreeNode node) {        if (node == null) return 0;                // 递归获取左右子树的深度        int leftDepth = depth(node.left);        int rightDepth = depth(node.right);                // 当前节点作为拐点的路径长度 = 左深度 + 右深度        diameter = Math.max(diameter, leftDepth + rightDepth);                // 返回当前节点的最大深度（用于上层调用）        return Math.max(leftDepth, rightDepth) + 1;    }}

使用示例

假设我们有如下二叉树：

      1     / \    2   3   / \  4   5

最长路径是 [4 -> 2 -> 5] 或 [5 -> 2 -> 1 -> 3]，但注意：直径定义为边的数量，所以 [4-2-5] 有2条边，[5-2-1-3] 有3条边，因此直径为3。

调用方式：

TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);TreeDiameter solver = new TreeDiameter();int result = solver.diameterOfBinaryTree(root);System.out.println("树的直径是: " + result); // 输出: 3

常见误区

• 误区1：认为直径一定经过根节点 —— 错！如上图，最长路径可能完全在左子树内部。
• 误区2：混淆“节点数”和“边数”—— LeetCode等平台通常以边数定义直径，务必看清题目要求。

总结

通过本篇数据结构教程，你已经掌握了如何用Java求解二叉树直径算法。核心思想是：在计算每个节点深度的同时，尝试将其作为路径的“最高点”，从而更新全局最长路径。这种“一边递归一边更新答案”的技巧，在树形DP中非常常见。

现在，你可以自信地应对任何关于Java树直径或树的最长路径Java的问题了！快去LeetCode上刷题巩固吧！