题目描述
思路解析
一句话答案：LeetCode 543 二叉树的直径用树形 DP 一趟后序遍历解决：每个节点把「左子树高度 + 右子树高度」当作穿过自己的最长路径去更新全局答案，但返回给父亲的是高度 1 + max(L, R)。直径不一定经过根，所以每个节点都要算一次。时间 O(n)，空间 O(h)。
二叉树的直径为什么不一定过根
直径的定义是：树中任意两个节点之间路径长度（边数）的最大值。直觉上最长的路好像该穿过根，其实不然——如果根的一侧子树特别深，最长路径完全可能在那棵子树内部的某个节点处「拐弯」，两头都扎向深处，根本碰不到根。所以任何只在根上算一次的做法都会漏解，必须让树里每个节点都有机会当一次「拐点」。
为什么想到在每个节点算左高加右高
观察最长路径的形状：它一定有一个位置最高的节点，路径在这里拐弯，一头沿左子树往下延伸、一头沿右子树往下延伸（也可能某一头长度为零）。以这个拐点为视角，路径的边数恰好等于「左子树的高度 + 右子树的高度」——每一侧能贡献的最长下探距离就是那侧子树的高度。
于是问题转化为：枚举每个节点作为拐点，算出它的 L + R，取全局最大值。而算某个节点的左右子树高度，本来就是一个经典的递归问题，两件事可以在同一趟遍历里一起做完，这正是树形 DP（在树上做动态规划）的味道。
返回值和答案为什么不是同一个数
这是本题最容易混的点。递归函数 height(node) 返回给父亲的是高度 1 + max(L, R)：站在父亲的角度，路径从父亲下来只能走进你的一条边、再沿着你的某一侧继续往下，所以你能贡献给父亲的只有「单边最深」那一条链。而 L + R 是左右两条链在你这里拼接、拐弯之后的完整路径——它已经拐过弯了，不能再交给父亲往上接，只能就地跟全局答案比大小。
参考代码里这两行各司其职：self.ans = max(self.ans, L + R) 负责收答案，return 1 + max(L, R) 负责给父亲供料。把两者混成一个（比如直接返回 L + R）会让父亲的高度整个算错。
为什么必须用后序遍历
每个节点的计算依赖左右孩子先给出各自的高度，不算完孩子就轮不到父亲——「左、右、根」的处理顺序正是后序遍历。执行时递归一路探到叶子，叶子左右皆空、高度 1、拼接值 0，然后逐层往上回传，每个节点顺手用自己的 L + R 刷一次全局最大值。一趟走完，答案就在全局变量里。
复杂度分析与易错边界
时间 O(n)：每个节点在后序遍历里恰好被访问一次，每次只做常数次比较加法。空间 O(h)：递归栈深度等于树高，最坏退化成链是 O(n)。
两个边界要留心：一是本题答案的口径是边数，若面试官改问「路径上的节点数」，只需在拼接值上加一；二是单节点树没有任何边，直径应为 0——全局答案初始化成 0、叶子的 L + R 恰好也是 0，这个初值天然兜住了该情况。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住：返回值（height）和更新答案用的值（左高+右高）不是同一个数——这是树形 DP 最容易混的点。
后序遍历：先把左子树彻底算完，再右子树，最后才轮到父亲。每个节点会留下两条记录：返回给父亲的「高度」、穿过自己的「路径=左高+右高」。
轮到节点 12（橙色）。它是叶子，左右子树都空，左高=0、右高=0。 这两个高度都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 12 算完（转绿）：穿过它的最长路径 = 左高 + 右高 = 0 + 0 = 0 条边（没超过当前最大 0）。但它返回给父亲的是 height = 1 + max(0, 0) = 1——注意这两个数不同：返回的是单边最深链，更新答案用的是左右拼起来。
轮到节点 8（橙色）。先读它两个孩子已经返回好的高度：左高 = 1，右子为空 → 右高 = 0。 这两个高度都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 8 算完（转绿）：穿过它的最长路径 = 左高 + 右高 = 1 + 0 = 1 条边（刷新了当前最大直径 → 1）。但它返回给父亲的是 height = 1 + max(1, 0) = 2——注意这两个数不同：返回的是单边最深链，更新答案用的是左右拼起来。
轮到节点 4（橙色）。先读它两个孩子已经返回好的高度：左高 = 2，右子为空 → 右高 = 0。 这两个高度都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 4 算完（转绿）：穿过它的最长路径 = 左高 + 右高 = 2 + 0 = 2 条边（刷新了当前最大直径 → 2）。但它返回给父亲的是 height = 1 + max(2, 0) = 3——注意这两个数不同：返回的是单边最深链，更新答案用的是左右拼起来。
轮到节点 13（橙色）。它是叶子，左右子树都空，左高=0、右高=0。 这两个高度都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 13 算完（转绿）：穿过它的最长路径 = 左高 + 右高 = 0 + 0 = 0 条边（没超过当前最大 2）。但它返回给父亲的是 height = 1 + max(0, 0) = 1——注意这两个数不同：返回的是单边最深链，更新答案用的是左右拼起来。
轮到节点 11（橙色）。先读它两个孩子已经返回好的高度：左高 = 0，右高 = 1。 这两个高度都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 11 算完（转绿）：穿过它的最长路径 = 左高 + 右高 = 0 + 1 = 1 条边（没超过当前最大 2）。但它返回给父亲的是 height = 1 + max(0, 1) = 2——注意这两个数不同：返回的是单边最深链，更新答案用的是左右拼起来。
轮到节点 5（橙色）。先读它两个孩子已经返回好的高度：左高 = 0，右高 = 2。 这两个高度都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 5 算完（转绿）：穿过它的最长路径 = 左高 + 右高 = 0 + 2 = 2 条边（刷新了当前最大直径 → 2）。但它返回给父亲的是 height = 1 + max(0, 2) = 3——注意这两个数不同：返回的是单边最深链，更新答案用的是左右拼起来。
轮到节点 2（橙色）。先读它两个孩子已经返回好的高度：左高 = 3，右高 = 3。 这两个高度都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 2 算完（转绿）：穿过它的最长路径 = 左高 + 右高 = 3 + 3 = 6 条边（刷新了当前最大直径 → 6）。但它返回给父亲的是 height = 1 + max(3, 3) = 4——注意这两个数不同：返回的是单边最深链，更新答案用的是左右拼起来。
轮到节点 3（橙色）。它是叶子，左右子树都空，左高=0、右高=0。 这两个高度都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 3 算完（转绿）：穿过它的最长路径 = 左高 + 右高 = 0 + 0 = 0 条边（没超过当前最大 6）。但它返回给父亲的是 height = 1 + max(0, 0) = 1——注意这两个数不同：返回的是单边最深链，更新答案用的是左右拼起来。
轮到节点 1（橙色）。先读它两个孩子已经返回好的高度：左高 = 4，右高 = 1。 这两个高度都是孩子在「自己那一帧」算好返回上来的——后序遍历保证算父亲前孩子一定先算完。
节点 1 算完（转绿）：穿过它的最长路径 = 左高 + 右高 = 4 + 1 = 5 条边（没超过当前最大 6）。但它返回给父亲的是 height = 1 + max(4, 1) = 5——注意这两个数不同：返回的是单边最深链，更新答案用的是左右拼起来。
全部算完。最大的「左高+右高」出现在拐点节点 2 上，值为 6。绿色加亮的就是这条最长路径——它在节点 2 处把左右两条最深链拼接起来，并不经过根节点 1。这正说明直径要靠「每个节点的左高+右高」逐个比较得出，而不是根的高度。
空 / 单点 / 退化链都被这套递归天然覆盖，按边数口径单点直径为 0。
认出这个「返回单边、全局拼接」的模板，一类树形 DP 题就通了。
参考代码
class Solution: def diameterOfBinaryTree(self, root): self.ans = 0 def height(node): if not node: return 0 L = height(node.left) # 左子树高度 R = height(node.right) # 右子树高度 self.ans = max(self.ans, L + R) # 穿过本节点的路径 return 1 + max(L, R) # 返回给父亲的是高度 height(root) return self.ans复杂度
- 时间：O(n)，每个节点只在后序里访问一次
- 空间：O(h)，递归栈深度 = 树高 h，最坏（退化成链）O(n)
易错点
面试追问把动画讲成自己的话
追问为什么用后序遍历而不是前序？
追问如果要的是「直径上的节点数」而不是边数怎么改？
追问这套「递归返回一个值、同时用副作用更新全局答案」的套路还能解什么？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
平衡二叉树
LeetCode 110 · 简单 · 沿着 树 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题