#543
简单
低频
后序 DFS二叉树的直径
这是一道围绕树、二叉树展开的高频练习。建议先掌握「后序 DFS」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
树
二叉树
题目分析
这道题表面上是在处理「二叉树的直径」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考 树、二叉树 这些能力。先别急着写代码，先把题目要求翻译成人话，明确结果是什么、约束是什么、过程里要持续维护什么。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：后序遍历时同时计算每个节点左右子树高度，并用
leftHeight + rightHeight 更新最大直径。推荐代码
推荐解法：后序 DFS
时间复杂度： O(n)
空间复杂度： O(h)
核心思路： 后序遍历时同时计算每个节点左右子树高度，并用
leftHeight + rightHeight 更新最大直径。class Solution {
private int diameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return diameter;
}
private int depth(TreeNode node) {
if (node == null) {
return 0;
}
int leftHeight = depth(node.left);
int rightHeight = depth(node.right);
diameter = Math.max(diameter, leftHeight + rightHeight);
return Math.max(leftHeight, rightHeight) + 1;
}
}结构化讲解
面试时怎么讲
开场思路
这题我会用后序 DFS，一边算高度，一边更新直径。
核心过程
- 递归求出左右子树高度。
- 经过当前节点的最长路径就是左高加右高。
- 用这个值更新全局最大直径。
- 然后把当前子树高度返回给父节点。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(h)。
面试补一句：这题要把“返回高度”和“更新直径”这两个职责区分开讲。
核心思路
二叉树直径不一定经过根节点，所以不能只在根上看。正确思路是对每个节点都计算“经过它的最长路径”，并在 DFS 过程中维护全局最大值。
步骤讲解
1
后序遍历计算子树高度
先拿到左右子树高度，再回到当前节点做计算。
为什么这样做：当前节点的直径候选值依赖左右子树高度。
对应代码提示：int leftHeight = depth(node.left);
2
用左右高度更新直径
经过当前节点的最长路径长度，就是左高加右高。
为什么这样做：一条路径最多只能从当前节点向左右各延伸一边。
对应代码提示：diameter = Math.max(diameter, leftHeight + rightHeight);
3
向父节点返回当前高度
当前节点高度等于左右子树较大高度再加 1。
为什么这样做：父节点只关心往下能延伸多深。
对应代码提示：return Math.max(leftHeight, rightHeight) + 1;
易错点
把直径误解成节点数
题目定义的直径是边数，不是路径上的节点数。
正确理解：这里直接用左右高度之和表示边数。
只比较经过根节点的路径
真正的最长路径可能完全在某个子树内部。
正确理解：在每个节点都更新一次全局答案。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(h)
比其他方案更好在哪里：比对每个节点单独再算一遍高度更高效，避免重复遍历。
适用判断：树题里既要向上返回局部信息，又要顺手更新全局答案时，后序 DFS 很常见。
额外提醒
- 返回值是高度，全局变量存的是直径，两者不要混在一起。