知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 05 - 二叉树的直径 ## 题目(LeetCode 543) 给定一棵二叉树,计算它的直径。直径是任意两个节点之间最长路径的边数。这条路径不一定经过根节点。 ``` 1 / \ 2 3 / \ 4 5 直径 = 3(路径:4 → 2 → 1 → 3,或 5 → 2 → 1 → 3) ``` ## 大白话理解 直径就是树里面最长的一条"弯路"。 关键洞察:对于任意一个节点,经过它的最长路径 = 它的左子树深度 + 右子树深度。 ``` 1 经过节点 1 的最长路径 = 左深度(2) + 右深度(1) = 3 / \ 2 3 经过节点 2 的最长路径 = 左深度(1) + 右深度(1) = 2 / \ 4 5 经过节点 4 的最长路径 = 0 + 0 = 0 ``` 所以我们遍历每个节点,算出经过它的最长路径,取全局最大值就是直径。 这和"求最大深度"几乎一样,只是在求深度的过程中顺便记录一下"左深度 + 右深度"的最大值。 ## 代码 ```java 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; } } ``` ### 为什么要用全局变量? 因为直径不一定经过根节点。可能在某个子树内部就有最长路径。所以我们需要在遍历过程中不断更新全局最大值。 ``` 反例:直径不经过根节点 1 / 2 / \ 3 4 / \ 5 6 直径 = 4(路径:5 → 3 → 2 → 4 → 6) 经过节点 2,不经过根节点 1 ``` ## 画图模拟 ``` 1 / \ 2 3 / \ 4 5 depth(4) → 左0 右0 → 直径=max(0, 0+0)=0 → 返回 1 depth(5) → 左0 右0 → 直径=max(0, 0+0)=0 → 返回 1 depth(2) → 左1 右1 → 直径=max(0, 1+1)=2 → 返回 2 depth(3) → 左0 右0 → 直径=max(2, 0+0)=2 → 返回 1 depth(1) → 左2 右1 → 直径=max(2, 2+1)=3 → 返回 3 最终直径 = 3 ✓ ``` ## 复杂度 - 时间:O(n) - 空间:O(h) ## 一句话总结 求深度的过程中,顺便记录"左深度 + 右深度"的最大值,就是直径。 --- 上一篇:[04 - 对称二叉树](./04-symmetric-tree.md) | 下一篇:[06 - 验证二叉搜索树](./06-validate-bst.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入