二叉树直径详解：递归与后序遍历求最长路径

二叉树的直径刷题路上绕不开的一道经典递归题。很多人第一次看到“直径”两个字下意识觉得是在求树里最远的两个节点之间的距离方向确实没错但真正动手写代码时却常常卡在“直径不一定经过根节点”这个点上。热门题单里的编号35说的就是这道题今天这篇就把它彻底拆开从定义、递推、代码到边界用例一次讲清楚。适合刚入门二叉树、准备面试、想把递归框架用熟练的同学也能帮已经会做的人补齐理解深度。1. 题目到底在问什么把“直径”翻译成人话1.1 从定义到直觉题目原文很简洁给定一棵二叉树返回它的直径。这里的直径定义为“任意两个节点之间路径长度中的最大值”而路径长度指的是两个节点之间的边的数量。很多人第一次看到“直径”会联想到几何里的圆的直径但在二叉树里完全没有这层意思它只看两个节点之间有多远。两个节点之间的路径是唯一的沿着父节点指针往上走总能找到一个公共祖先路径就是从节点A上溯到祖先再下探到节点B。路径上穿过的边的条数就是这两个节点之间的距离。一棵树的直径就是所有节点对之间距离的最大值。换句话说找两个点让它们之间的边数尽可能多。这里有个容易忽略的点题目没有限定“路径必须经过根节点”。恰恰相反很多最大距离出现在某个子树的内部和根节点一点关系都没有。下面用一个最简单的反例就能看清。1.2 最常见的误区直径必须过根节点假设有一棵只有右子树的链状树根节点1右孩子2右孩子3右孩子4。整棵树退化成一条直线一共有4个节点3条边。直觉上最远的两个节点是1和4距离是3这条路径确实经过根节点1。但如果把根节点往旁边挪一下变成一棵稍微深一点的树比如根节点的左子树很深右子树也很深但左右深度不对称情况就不一样了。更典型的反例是这样的根节点1左孩子2右孩子3。2下面挂一个左孩子44下面挂一个左孩子53下面挂一个右孩子66下面挂一个右孩子7。这棵树的左右子树都很深最远节点显然是5和7路径是5—4—2—1—3—6—7经过根节点直径是5。但如果把根节点的左右子树深度做成“一边特别深另一边特别浅”真正的最远点对可能完全落在某一条链上根本不需要经过根节点。比如一棵退化成单链的树链的两端距离最远但其中间路径可能穿过一些祖先节点如果直径计算时只考虑经过当前根节点的路径就会漏掉真正的答案。所以在做这道题时千万不要把代码写成“只求左子树高度加右子树高度”。这是初学者最常见的错误也是这道题专门设置的坑。1.3 先算深度再求直径树的高度是基础材料要理解直径解法先得把“深度”和“高度”这两个概念理顺。不同资料里叫法有点混这里统一说明深度从根节点到当前节点的边的数量。高度从当前节点到最远叶子节点的边的数量。直径的候选路径可以看作“某个节点左子树中最深的叶子”到“右子树中最深的叶子”的距离。这条路径在这个节点处拐了一个弯而这个节点就是路径上最高最靠近根的那个点。对于任意节点X经过X且以X为“最高点”的路径长度等于左子树高度加右子树高度。因为从左子树最深叶子走到X需要左子树高度条边从X走到右子树最深叶子需要右子树高度条边加起来就是整条路径的边数。整棵树的直径就是所有节点上这个“左高右高”的最大值。这样就把一个求距离的问题转换成了求每个子树高度的问题。高度怎么求递归非常自然一个空节点高度为0非空节点的高度是左右子树高度的最大值再加1。这是二叉树递归的基石也是后面所有解法的核心递归函数。2. 解题前的底层准备遍历与递归框架2.1 为什么树的问题天然适合递归二叉树本身就是递归定义的一棵二叉树要么为空要么由一个根节点和两棵二叉树组成。这个定义让递归解法成为一种“顺手”的选择。用生活里的例子理解公司里要统计一个部门的最高工时部门经理只需要问两个组长的最高工时取较大值然后加上自己的一小时。组长再去问下面的员工。每一层做的事情一模一样只是范围变小了。递归函数就是这样一个自动化的层级汇报机制。在二叉树上每个节点只需要关心两件事左子树返回什么信息右子树返回什么信息然后结合自己当前节点的信息决定向上层返回什么。这种“自底向上”的信息传递天然对应树的递归结构。很多树相关的题目比如最大深度、平衡二叉树、直径、路径总和本质都是同一个递归框架在不同信息维度上的变体。把递归树的推导练熟等于拿到一把万能钥匙。2.2 后序遍历自底向上汇总信息树的遍历有前序、中序、后序三种经典顺序。直径这道题需要的是后序遍历。后序遍历的顺序是先遍历左子树再遍历右子树最后处理当前节点。为什么直径需要后序因为计算当前节点的“左高右高”时必须已经知道左子树和右子树各自的高度而这些高度又需要先递归求解。换句话说当前节点的答案依赖子树的结果必须先把子树算完再回头算当前节点。这正是后序顺序的定义。前序遍历适合“从根开始向下传递信息”的场景比如求根节点到所有节点的路径和。后序遍历适合“从叶子向上汇总信息”的场景比如求子树高度、最大直径、子树和。用错了遍历顺序代码逻辑就会别别扭扭甚至完全失效。2.3 全局变量与函数返回值两种风格的取舍递归函数需要同时完成两个任务向上返回子树高度同时在每个节点尝试更新直径答案。这两个任务的信息方向不同实现上有两种常见选择。第一种递归函数只返回子树高度直径用外部变量记录。每次访问到节点X时用左右子树高度之和去更新外部变量。这种做法直观代码清晰面试时最容易讲明白。第二种递归函数返回一个结构体或pair同时包含“本子树高度”和“本子树内部最大直径”。这样做的好处是没有全局变量纯函数风格适合一些面试官较真的场合或者做单元测试时更干净。两种写法等价但理解第一种是基础。因为第一种把“向上返回”和“全局更新”两个责任分得很清楚初学者不容易绕晕。3. 完整解法递归DFS的推演与代码实现3.1 状态定义与递推关系明确一个递归函数dfs(node)返回以node为根节点的子树的最大高度从根到最远叶子的边数。递推关系如果node为空返回0。否则递归求左子树高度L dfs(node-left)右子树高度R dfs(node-right)。当前节点作为路径最高点时经过它的最长路径长度为L R。用这个值更新全局答案diameter max(diameter, L R)。向上一层返回max(L, R) 1表示当前子树的高度。整个过程只需要遍历一次所有节点时间复杂度O(n)。每个节点都做常数次操作没有任何重复计算。理解递推关系的关键点在于L R只是“途经当前节点的最长路径”并不是当前子树最终的直径答案。子树最终的直径可能完全在左子树内部也可能完全在右子树内部因此全局答案必须取所有L R的最大值。3.2 边界条件处理边界条件就是空节点。空节点没有高度返回0。如果整棵树为空dfs(root)会被调用一次左右子树都是空L R 0全局答案保持初始值0返回0结果正确。只有一个根节点时左右子树为空L R 0答案也是0。两个节点的树比如根1左孩子2根节点的左子树高度1右子树高度0L R 1答案1正好是1到2的边数。边界处理最常见的坑是把空节点返回-1。有些算高度的问题会返回-1来配合某类平衡判断但直径这道题统一返回0最简单也符合“高度边数”的定义。3.3 核心代码实现以常见的二叉树结构为例struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; class Solution { public: int diameter 0; int dfs(TreeNode* root) { if (root nullptr) { return 0; } int leftHeight dfs(root-left); int rightHeight dfs(root-right); // 经过当前节点的最长路径 左子树高度 右子树高度 diameter max(diameter, leftHeight rightHeight); // 返回当前子树的高度 return max(leftHeight, rightHeight) 1; } int diameterOfBinaryTree(TreeNode* root) { diameter 0; dfs(root); return diameter; } };提示每次调用diameterOfBinaryTree时都要把全局变量重置为0。否则如果同一个Solution实例被多次调用上一次的结果会污染下一次答案。这里用成员变量保存直径是为了让dfs函数只承担“返回高度”这一个职责。实际提交时这种做法非常稳定不容易出错。3.4 不使用全局变量的写法有些场景下比如面试官要求写一个纯函数不希望有外部状态就可以用返回值同时携带高度和直径pairint, int dfsWithDiameter(TreeNode* root) { if (root nullptr) { return {0, 0}; } auto left dfsWithDiameter(root-left); auto right dfsWithDiameter(root-right); int height max(left.first, right.first) 1; int diameter max(left.second, max(right.second, left.first right.first)); return {height, diameter}; } int diameterOfBinaryTree(TreeNode* root) { return dfsWithDiameter(root).second; }这里的pair第一个值表示子树高度第二个值表示子树内部的直径。每个节点返回给父节点的直径可能是左子树直径、右子树直径、或者“左高右高”三者中的最大值。这种写法和全局变量版本完全等价只是把状态封装在了递归返回值里。我在做单元测试时喜欢用这个版本因为可以反复调用同一个函数不用考虑重置状态。3.5 复杂度分析时间复杂度O(n)n是节点总数。因为每个节点只被访问一次递归函数在每个节点上的操作是常数时间。空间复杂度O(h)h是树的高度。递归需要调用栈空间最坏情况下树退化成一个链递归深度等于节点数空间O(n)。平均情况下树的高度远小于节点数空间占用没问题。要特别注意这里的空间复杂度不是O(1)递归栈也是成本。某些极端情况下10万个节点的单链树会导致递归层数达到10万可能会栈溢出。不过面试和笔试的常规用例不会这么极端知道结论即可。4. 从“会做”到“做对”边界用例与高频错误4.1 测试用例设计做题不能只靠平台给的几个样例自己要在本地多构造边界情况。我最常用的一组用例空树nullptr期望结果0。单节点只有一个根期望0。两节点根和左孩子期望1。三节点链1-2-3期望2。左右子树各一条深链根左边挂一条深度4的链右边挂一条深度3的链期望7。完全二叉树7个节点的满二叉树最远叶子之间的距离是4期望4。最后一类用例很关键完全二叉树里最深的两个叶子隔着根节点距离是左子树高度2加右子树高度2等于4。如果代码只在某个节点计算左右高度完全二叉树能过但链状树可能出错。所以一定要把链状树单独测一遍。还有一类“隐藏用例”左子树很深但右子树为空直径其实完全在左子树内部。这种情况下如果代码只算根节点的左高右高会漏掉左子树内部的更长路径。正确解法靠全局更新天然覆盖这种情况。4.2 高频Bug清单我在带人做这道题时看过不少重复踩坑的写法整理成清单第一个Bug只计算根节点的左高右高。这是最经典的错误虽然题目本身没有强调但平台用例里一定有一棵“直径不经过根节点”的树来卡你。比如根节点右子树是空左子树是一棵很深的树真实直径可能在左子树的内部。只算根节点会得到一个小得多的错误答案。第二个Bug递归返回时忘了加1。有人写return max(leftHeight, rightHeight);导致每个节点的高度都少算一层最终答案偏小。记住“当前节点也算一层”必须加1。第三个Bug更新直径的时机不对。有人把diameter max(diameter, leftHeight rightHeight)写在了递归调用之前此时左右高度还没计算出来得到的永远是0。第四个Bug空节点返回-1。这个习惯是从“计算二叉树平衡因子”那类题带过来的。在直径问题里空节点返回0才能让单节点树的直径正确为0如果返回-1单节点树会得到-2之类的负数还得额外打补丁。第五个Bug重复递归。有人在diameterOfBinaryTree里先递归一遍求左子树直径再递归一遍求右子树直径又递归求左右深度。这样做功能上勉强对但时间复杂度变成O(n^2)遇到底层链状树直接超时。记住一次后序遍历就够。第六个Bug路径长度理解成节点数。题目要的是边数。每次直径都是左右高度之和这个值天然是边数别在最后结果上再加1或减1。4.3 迭代法可行吗递归是这道题最自然的解法但总有人问“能不能用迭代做”。答案是能思路是用栈模拟后序遍历。迭代后序遍历需要维护每个节点对应的高度。一个简单做法是同时压栈两次或者手动模拟递归栈帧记录节点状态。具体步骤大致是用栈保存节点并标记是否已经访问过左右子树。当左右子树都处理后计算当前节点的左高右高更新答案。当前节点向上返回的高度可以存在一个哈希表里键是节点指针值是高度。代码会比递归版本长不少唯一的优势是避免递归栈溢出。但在绝大多数面试场景下递归版本足够而且代码更短更容易解释。我一般会主动提一句“如果树很深递归可能爆栈可以用栈模拟后序遍历”显示你考虑过工程化问题但不会真的现场写迭代版。5. 举一反三一道题带出整个树形DP脉络5.1 从直径到最大路径和二叉树的直径不带权只看边长。把它升级一下就变成经典的“二叉树中的最大路径和”每个节点有一个整数值路径上所有节点值的和定义为路径和求最大路径和。解法和直径如出一辙区别在于直径里空节点的高度是0路径长度不会为负。最大路径和里节点值可能是负数一个子树如果和是负的就不如不选这个子树。递归函数在更新答案时要计算“左子树最大贡献 右子树最大贡献 当前节点值”但向上返回时只能返回“单侧最大贡献 当前节点值”并且如果这个值是负数就返回0等价于放弃这个分支。直径题不需要考虑负数所以边界判断少一点。但从直径迁移到最大路径和逻辑框架完全一致只要学会处理“值可能为负”的三种情况就通了。5.2 从直径到最长同值路径另一个变体是“最长同值路径”路径上的所有节点值必须相同求这样的路径最长能有多少条边。思路依然是用后序遍历对每个节点计算“从当前节点出发、沿着相同值向下延伸的最大长度”。但更新答案时只有左孩子值和当前节点值相同才把左子树贡献加进来右孩子同理。返回给父节点的高度也只考虑与父节点值相同的分支。这里的关键是“相同值”这个约束让左右子树的贡献变成了条件值而不是无条件累加。理解了直径题的“任意贡献”和同值路径题的“条件贡献”再看很多树形DP问题就会觉得眼熟。5.3 扩展到N叉树的直径如果二叉树变成N叉树每个节点可能有很多孩子直径怎么求思路还是类似的对每个节点找孩子中最大的两个高度它们的和就是经过当前节点的最长路径。需要维护一个“前两大高度”而不是简单的左加右。实现时递归函数返回当前子树的最大高度同时遍历所有孩子记录最大和次大的高度用最大次大更新全局答案。其实二叉树的leftHeight rightHeight就是“孩子高度中最大和次大的和”因为二叉树最多两个孩子最大和次大恰好是左右子树。理解这一层后从二叉到N叉就是自然的扩展。5.4 本质子树信息汇总的树形DP回看这些变体核心思想一致每个节点根据子节点返回的信息结合自身计算出本子树的某种指标并把子问题最关心的信息继续向上传递。这就是最基础的树形DP。和普通DP的区别只是“阶段”变成了“树的层级”决策顺序受树的拓扑结构约束。二叉树的直径是树形DP里最典型的入门题因为它没有任何状态压缩、没有权值、没有条件纯粹展示“后序汇总”这个骨架。很多人觉得树形DP难其实从这一题开始做通后面遇到打家劫舍III、监控二叉树、树的最大独立集都能找到熟悉的感觉。6. 实战心得与避坑经验6.1 面试中怎么讲这道题如果面试遇到这道题不要拿到手就闷头写代码。先在白板上画一棵比较复杂的树比如左右子树深度不同的那种指着它讲清楚思路先定义dfs返回子树高度然后用一个全局变量记录所有节点中“左高右高”的最大值。为什么不是只算根节点因为直径可能完全落在子树内部必须遍历所有节点。讲的时候主动写一个反例证明“只算根节点”为什么错。这个细节能让面试官对你的理解深度刮目相看。代码写完后主动报复杂度时间O(n)空间O(h)。如果面试官追问能不能优化可以提迭代版模拟后序或者说O(h)已经是递归的常规下限无法做到O(1)且不改变树结构。还有一个小话术解释返回值“高度”和答案“直径”是两个不同维度。高度是给父节点用的中间信息直径是全局累计答案。把这两个概念分开讲面试官基本不会觉得你是在背题。6.2 三个能立刻上手的验证技巧做完代码后我一般会做三件事来验证正确性第一步手推样例。画一棵三层的树手动计算高度和直径再拿代码结果对比。第二步跑极端用例。比如空树、单节点、退化成链的树这些用例容易暴露“返回-1”“忘加1”之类的问题。第三步尝试改动代码确认理解。比如把更新答案的语句删掉答案会变成0把返回值改成不加1所有高度都错。故意破坏代码再观察结果是检验自己是否理解递归逻辑的好方法。这三个技巧听起来简单但能很大程度减少“代码在平台上跑过就觉得会了”的假象。真正把每一行为什么存在的理由讲清楚才算掌握。6.3 我自己的体会这道题我前后刷过好几遍每次重看都有新的理解。第一遍时我只记得“左右高度相加”但遇到直径不经过根节点的用例就懵了。第二遍才真正明白全局更新的必要性。第三遍能主动和最大路径和、最长同值路径串起来想。从刷题角度说二叉树直径的价值不在于题目本身有多难而在于它是“递归后序处理”这个母题的最佳样品。把这道题吃透后面一大批树的题都会轻松很多。从面试角度说这道题代码量小、思路清晰、坑点明确是一道性价比极高的热身题。如果你正在准备面试建议把这题放在二叉树专题的前面先把它的递归框架练成肌肉记忆再往后推进。