题目描述
思路解析
一句话答案：LeetCode 687 最长同值路径：后序 DFS 让每个孩子先交上向下的同值单臂，本节点用左臂加右臂刷答案、只把更长的单臂返给父亲，省掉每点重复下探，时间 O(n)。
同值路径数的是边，不是节点
给一棵二叉树 root，找一条路径，路径上每个节点的值都相等，返回它的边数，注意是边数不是节点数，5 个同值点连成一串算 4 条边。这条路径可以经过根，也可以整个躲在某棵子树里。题面 root=[5,4,5,1,1,5] 答案是 2，走的是右边 5-5-5 三个点两条边；root=[50,50,50,90,50,null,50] 答案是 4。
拿每个点当拐点向下探，深链会被反复数
路径能在任何一个节点拐弯，所以得让每个节点都当一次拐点：从它向左、向右各伸一条同值链，两条拼起来取最大。麻烦在于，量一个点向下的同值链要从它一路探到底；而它的孩子、孙子当拐点时，同一段链又被各自重探一遍。长链上的节点被翻来覆去数，最坏要 O(n²)。
让孩子先算完，把向下的单臂交上来
换个次序就能省掉重探。一个节点向下的最长同值链，只取决于它两个孩子向下的同值链，跟更上面的节点无关。于是改走后序 DFS：先递归两个孩子、拿到它们向下的链长，轮到当前节点时直接取用，不必重新下探。每个节点只在轮到自己时结算一次，一趟遍历搞定，时间落到 O(n)。
向下的单臂和跨过顶点的整条路，是两回事
递归函数返回一个数：从当前节点向下、值一路相同的最长链有多长，按边数计。规则是这样：左孩子存在且值和当前节点相等，左臂 l 就是左孩子返回值加一，否则记 0；右臂 r 同理看右孩子。
接着要分清两种量。过当前节点的同值路径允许从左臂拐到右臂，长度是 l+r，拿去刷新全局答案 ans；可返回给父亲的绝不能是 l+r——路径从父亲下来进了这个节点，只能继续朝一个孩子的方向延伸，在这里拐弯分叉就不成其为路径了。所以往上只交 max(l, r)，两条臂里更长的那条。
拿 [5,4,5,1,1,5] 自底向上把每个节点的臂长结清
根是 5，左孩子 4 挂着两个叶子 1，右孩子 5 底下带一个叶子 5。后序先落到最底：两个叶子 1 向下无边，各返回 0；它们的父亲 4，左右孩子都是 1、和 4 不同值，两臂都归零，l+r=0，返回 0。
再看右边：叶子 5 返回 0；它父亲那个 5，左孩子 5 同值，左臂 l=0+1=1，没有右孩子 r=0，过它的路径 l+r=1，ans 刷成 1，上交 max(1, 0)=1。回到根 5：左孩子 4 不同值、左臂归零，右孩子 5 同值、右臂 r=1+1=2，过根的路径 l+r=0+2=2，ans 更新为 2，返回 max(0, 2)=2。跑完 ans=2，正是 5-5-5 那两条边。
空树、单点都是 0，最坑的是把边数成点数
复杂度上，每个节点后序访问、结算一次，做的是常数次比较和加法，时间 O(n)；额外开销只有递归栈，深度就是树高 h——匀称时压到 O(log n)，退化成一条链则到 O(n)。边界很干净：空树没有节点，答案 0；单个节点没有边，答案也是 0。
最常见的写反，是把返回值贪成 l+r 交给父亲——父亲据此会拼出一条分叉、实际走不通的路径，返回值必须收成 max(l, r)。另一处是把答案报成节点个数，可题目量的是边：5 个同值点之间只有 4 条边，数成 5 就整整多出一条。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记死这句：经过点取左臂加右臂刷答案，往上只返回更长的单臂。后面每帧都在套它。
准备 · 后序遍历顺序：先看清这棵树。根是 50，左右孩子也都是 50，只有左下角那个 90 跟大家不一样。后序 DFS 会一路下探到叶子，从最底下往上、一个个把节点结算掉。紫色是正在处理的节点，结算完会变绿。
下行 · 进入节点 50：下探到值为 50 的这个节点（紫色）。它还有孩子，得先把左右孩子递归算完，才能轮到它。
下行 · 进入节点 50：下探到值为 50 的这个节点（紫色）。它还有孩子，得先把左右孩子递归算完，才能轮到它。
下行 · 进入节点 90：下探到值为 90 的这个节点（紫色）。它没有孩子，是叶子，可以直接结算。
叶子 · 节点 90 返回 0：叶子 90 向下一条边都没有，所以它给父亲的单臂长度是 0。它结算完毕，变绿。
下行 · 进入节点 50：下探到值为 50 的这个节点（紫色）。它没有孩子，是叶子，可以直接结算。
叶子 · 节点 50 返回 0：叶子 50 向下一条边都没有，所以它给父亲的单臂长度是 0。它结算完毕，变绿。
结算左臂 · 看左孩子 90：看左孩子，它的值是 90，跟当前的 50 不一样，这条边断掉，标红。所以左臂只能归零。
结算右臂 · 看右孩子 50：再看右孩子，值同样是 50，同值，边接得上。右臂 = 右孩子返回的 0 加一条边 = 1。
经过 50 的路径 = 左 0 + 右 1 = 1：把左臂 0 和右臂 1 拼起来，就是经过这个节点的最长同值路径，共 1 条边（紫路径）。它比之前的 ans 大，刷新答案为 1。
返回 · 节点 50 上交单臂 1：结算完，它要回到父亲那一层。注意往上只能交一条臂，因为路径到了父亲不能在这里分叉，所以返回左右臂里更长的那条 = 1。本节点变绿，结束。
下行 · 进入节点 50：下探到值为 50 的这个节点（紫色）。它还有孩子，得先把左右孩子递归算完，才能轮到它。
下行 · 进入节点 50：下探到值为 50 的这个节点（紫色）。它没有孩子，是叶子，可以直接结算。
叶子 · 节点 50 返回 0：叶子 50 向下一条边都没有，所以它给父亲的单臂长度是 0。它结算完毕，变绿。
结算左臂 · 没有左孩子：当前节点没有左孩子，左边没有可延伸的臂，左臂记 0。
结算右臂 · 看右孩子 50：再看右孩子，值同样是 50，同值，边接得上。右臂 = 右孩子返回的 0 加一条边 = 1。
经过 50 的路径 = 左 0 + 右 1 = 1：把左臂 0 和右臂 1 拼起来，就是经过这个节点的最长同值路径，共 1 条边（紫路径）。它没超过已有的 ans = 1，答案保持不变。
返回 · 节点 50 上交单臂 1：结算完，它要回到父亲那一层。注意往上只能交一条臂，因为路径到了父亲不能在这里分叉，所以返回左右臂里更长的那条 = 1。本节点变绿，结束。
结算左臂 · 看左孩子 50：看左孩子，它的值也是 50，跟当前节点同值，这条边接得上。于是左臂 = 左孩子返回的 1 再加这一条边 = 2。左孩子标成路径色。
结算右臂 · 看右孩子 50：再看右孩子，值同样是 50，同值，边接得上。右臂 = 右孩子返回的 1 加一条边 = 2。
经过 50 的路径 = 左 2 + 右 2 = 4：把左臂 2 和右臂 2 拼起来，就是经过这个节点的最长同值路径，共 4 条边（紫路径）。它比之前的 ans 大，刷新答案为 4。
返回 · 节点 50 上交单臂 2：结算完，它要回到父亲那一层。注意往上只能交一条臂，因为路径到了父亲不能在这里分叉，所以返回左右臂里更长的那条 = 2。本节点变绿，结束。
完成 · 最长同值路径：所有节点都结算完了。全局最长的「经过点」路径是紫色这条 50-50-50-50-50，从左下的 50 经过根再到右下的 50，正好 4 条边。那个 90 跟周围不同值，谁也接不上它，被排除在外。这就是答案。
边界先想清:空树和单点都是 0 条边；有重复值时找最长那一段。
面试高频:和直径同骨架、返回单臂的原因。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def longestUnivaluePath(self, root: Optional[TreeNode]) -> int: def dfs(root: Optional[TreeNode]) -> int: if root is None: return 0 l, r = dfs(root.left), dfs(root.right) l = l + 1 if root.left and root.left.val == root.val else 0 r = r + 1 if root.right and root.right.val == root.val else 0 nonlocal ans ans = max(ans, l + r) return max(l, r) ans = 0 dfs(root) return ans复杂度
- 时间：O(n)，每个节点只被后序访问并结算一次，常数次比较与加法
- 空间：O(h)，递归栈深 = 树高 h；最坏退化成链时 O(n)，平衡时 O(log n)
易错点
面试追问把动画讲成自己的话
追问这题和「二叉树的直径」LeetCode 543 有什么关系？
追问为什么不能在递归里直接返回左臂加右臂？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
员工的重要性
LeetCode 690 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题