一、题目描述给你一棵二叉树的根节点root返回该树的直径。二叉树的直径 是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点。⚠️ 路径长度 节点之间的边数不是节点数。示例一输入root [1,2,3,4,5] 输出3对应二叉树1 / \ 2 3 / \ 4 5✅ 最长路径4 → 2 → 5或4 → 2 → 1 → 3路径长度 3 条边示例二输入root [1,2] 输出11 / 2✅ 最长路径2 → 1长度 1示例三输入root [] 输出0空树直径为 0。二、为什么这道题值得学这道题表面是“求直径”实际考的是递归思维后序遍历左右根全局变量的使用对“路径定义”的精确理解它是LeetCode 104最大深度 的升级版也是面试中非常爱问的一道“递归陷阱题”。三、核心思想重点❗ 一个极易混淆的点直径 ≠ 树的深度很多人第一反应是return maxDepth(root) - 1; // ❌ 错误这是错的因为最长路径不一定经过根节点。✅ 正确理解对任意一个节点node经过node的最长路径长度 左子树的最大深度 右子树的最大深度而整棵树的直径 max(所有节点的“左右深度之和”)递归定义设函数depth(node)表示以node为根的子树的最大深度边数那么depth(node) 1 max(depth(node.left), depth(node.right))并在递归过程中用一个全局变量 记录diameter max(diameter, leftDepth rightDepth)四、解法一DFS 全局变量面试首选 ✅思路图解以这棵树为例1 / \ 2 3 / \ 4 5递归顺序后序遍历计算4左 0 右 0 → 更新直径候选 0计算5左 0 右 0 → 更新直径候选 0计算2左 1 右 1 → 更新直径候选 2计算3左 0 右 0 → 更新直径候选 2计算1左 2 右 1 → 更新直径候选 3 ✅最终直径 3Java 实现class Solution { // 全局变量记录最大直径 private int maxDiameter 0; public int diameterOfBinaryTree(TreeNode root) { depth(root); return maxDiameter; } // 返回当前节点的高度边数 private int depth(TreeNode node) { if (node null) { return 0; } int leftDepth depth(node.left); int rightDepth depth(node.right); // 更新最大直径 maxDiameter Math.max(maxDiameter, leftDepth rightDepth); // 返回当前节点的高度 return Math.max(leftDepth, rightDepth) 1; } }复杂度分析指标复杂度时间复杂度O(n)空间复杂度O(h)每个节点只访问一次递归栈深度 树高h五、常见错误面试高频踩坑❌ 错误一把直径当成深度return depth(root) - 1; // ❌只适用于“必须经过根节点”的情况。❌ 错误二忘了用全局变量return leftDepth rightDepth; // ❌这只计算了根节点的直径忽略了子树内部的最长路径。❌ 错误三深度定义混乱有的写法深度 节点数有的写法深度 边数⚠️本题明确要求边数六、面试高频追问1️⃣ 这和 LeetCode 104最大深度有什么关系104只关心根节点深度543要维护一个全局最大值2️⃣ 为什么要用全局变量因为直径信息不能在单次递归返回值中体现必须跨递归调用共享。3️⃣ 能不能不用全局变量✅ 可以用int[]或自定义类包装结果但可读性不如全局变量。4️⃣ 如果要求“必须经过根节点”怎么办那就退化为depth(root.left) depth(root.right)七、一句话总结二叉树的直径 所有节点的「左深度 右深度」的最大值记忆口诀后序遍历算深度左右相加记全局
LeetCode 543 二叉树的直径：为什么答案不是树的深度？一文彻底讲透
一、题目描述给你一棵二叉树的根节点root返回该树的直径。二叉树的直径 是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点。⚠️ 路径长度 节点之间的边数不是节点数。示例一输入root [1,2,3,4,5] 输出3对应二叉树1 / \ 2 3 / \ 4 5✅ 最长路径4 → 2 → 5或4 → 2 → 1 → 3路径长度 3 条边示例二输入root [1,2] 输出11 / 2✅ 最长路径2 → 1长度 1示例三输入root [] 输出0空树直径为 0。二、为什么这道题值得学这道题表面是“求直径”实际考的是递归思维后序遍历左右根全局变量的使用对“路径定义”的精确理解它是LeetCode 104最大深度 的升级版也是面试中非常爱问的一道“递归陷阱题”。三、核心思想重点❗ 一个极易混淆的点直径 ≠ 树的深度很多人第一反应是return maxDepth(root) - 1; // ❌ 错误这是错的因为最长路径不一定经过根节点。✅ 正确理解对任意一个节点node经过node的最长路径长度 左子树的最大深度 右子树的最大深度而整棵树的直径 max(所有节点的“左右深度之和”)递归定义设函数depth(node)表示以node为根的子树的最大深度边数那么depth(node) 1 max(depth(node.left), depth(node.right))并在递归过程中用一个全局变量 记录diameter max(diameter, leftDepth rightDepth)四、解法一DFS 全局变量面试首选 ✅思路图解以这棵树为例1 / \ 2 3 / \ 4 5递归顺序后序遍历计算4左 0 右 0 → 更新直径候选 0计算5左 0 右 0 → 更新直径候选 0计算2左 1 右 1 → 更新直径候选 2计算3左 0 右 0 → 更新直径候选 2计算1左 2 右 1 → 更新直径候选 3 ✅最终直径 3Java 实现class Solution { // 全局变量记录最大直径 private int maxDiameter 0; public int diameterOfBinaryTree(TreeNode root) { depth(root); return maxDiameter; } // 返回当前节点的高度边数 private int depth(TreeNode node) { if (node null) { return 0; } int leftDepth depth(node.left); int rightDepth depth(node.right); // 更新最大直径 maxDiameter Math.max(maxDiameter, leftDepth rightDepth); // 返回当前节点的高度 return Math.max(leftDepth, rightDepth) 1; } }复杂度分析指标复杂度时间复杂度O(n)空间复杂度O(h)每个节点只访问一次递归栈深度 树高h五、常见错误面试高频踩坑❌ 错误一把直径当成深度return depth(root) - 1; // ❌只适用于“必须经过根节点”的情况。❌ 错误二忘了用全局变量return leftDepth rightDepth; // ❌这只计算了根节点的直径忽略了子树内部的最长路径。❌ 错误三深度定义混乱有的写法深度 节点数有的写法深度 边数⚠️本题明确要求边数六、面试高频追问1️⃣ 这和 LeetCode 104最大深度有什么关系104只关心根节点深度543要维护一个全局最大值2️⃣ 为什么要用全局变量因为直径信息不能在单次递归返回值中体现必须跨递归调用共享。3️⃣ 能不能不用全局变量✅ 可以用int[]或自定义类包装结果但可读性不如全局变量。4️⃣ 如果要求“必须经过根节点”怎么办那就退化为depth(root.left) depth(root.right)七、一句话总结二叉树的直径 所有节点的「左深度 右深度」的最大值记忆口诀后序遍历算深度左右相加记全局
