LeetCode 687中等树 · BST

最长同值路径图解题解

这道题到底在问什么

给定二叉树 root，求一条路径，路径上每个节点的值都相等，返回这条路径的边数（不是节点数）。路径可经过也可不经过根节点。

输入: root=[5,4,5,1,1,5]
输出: 2
输入: root=[50,50,50,90,50,null,50]（本帧这棵）
输出: 4

最优解：一步一步想明白

3记死这句：经过点取左臂加右臂刷答案，往上只返回更长的单臂。后面每帧都在套它。
4从根下探，叶子先结算先看清这棵树。根是 50，左右孩子也都是 50，只有左下角那个 90 跟大家不一样。后序 DFS 会一路下探到叶子，从最底下往上、一个个把节点结算掉。紫色是正在处理的节点，结算完会变绿。
5处理 idx 0下探到值为 50 的这个节点（紫色）。它还有孩子，得先把左右孩子递归算完，才能轮到它。
6处理 idx 1下探到值为 50 的这个节点（紫色）。它还有孩子，得先把左右孩子递归算完，才能轮到它。
7处理 idx 3下探到值为 90 的这个节点（紫色）。它没有孩子，是叶子，可以直接结算。
8idx 3 臂长 0叶子 90 向下一条边都没有，所以它给父亲的单臂长度是 0。它结算完毕，变绿。
9处理 idx 4下探到值为 50 的这个节点（紫色）。它没有孩子，是叶子，可以直接结算。
10idx 4 臂长 0叶子 50 向下一条边都没有，所以它给父亲的单臂长度是 0。它结算完毕，变绿。
11不同 → 左臂 0看左孩子，它的值是 90，跟当前的 50 不一样，这条边断掉，标红。所以左臂只能归零。
12同值 → 右臂 1再看右孩子，值同样是 50，同值，边接得上。右臂 = 右孩子返回的 0 加一条边 = 1。
13刷新答案 ans = 1把左臂 0 和右臂 1 拼起来，就是经过这个节点的最长同值路径，共 1 条边（紫路径）。它比之前的 ans 大，刷新答案为 1。
14往上只返回 max(0, 1) = 1结算完，它要回到父亲那一层。注意往上只能交一条臂，因为路径到了父亲不能在这里分叉，所以返回左右臂里更长的那条 = 1。本节点变绿，结束。
15处理 idx 2下探到值为 50 的这个节点（紫色）。它还有孩子，得先把左右孩子递归算完，才能轮到它。
16处理 idx 6下探到值为 50 的这个节点（紫色）。它没有孩子，是叶子，可以直接结算。
17idx 6 臂长 0叶子 50 向下一条边都没有，所以它给父亲的单臂长度是 0。它结算完毕，变绿。
18左臂 0当前节点没有左孩子，左边没有可延伸的臂，左臂记 0。
19同值 → 右臂 1再看右孩子，值同样是 50，同值，边接得上。右臂 = 右孩子返回的 0 加一条边 = 1。
20不超过 ans = 1把左臂 0 和右臂 1 拼起来，就是经过这个节点的最长同值路径，共 1 条边（紫路径）。它没超过已有的 ans = 1，答案保持不变。
21往上只返回 max(0, 1) = 1结算完，它要回到父亲那一层。注意往上只能交一条臂，因为路径到了父亲不能在这里分叉，所以返回左右臂里更长的那条 = 1。本节点变绿，结束。
22同值 → 左臂 2看左孩子，它的值也是 50，跟当前节点同值，这条边接得上。于是左臂 = 左孩子返回的 1 再加这一条边 = 2。左孩子标成路径色。
23同值 → 右臂 2再看右孩子，值同样是 50，同值，边接得上。右臂 = 右孩子返回的 1 加一条边 = 2。
24刷新答案 ans = 4把左臂 2 和右臂 2 拼起来，就是经过这个节点的最长同值路径，共 4 条边（紫路径）。它比之前的 ans 大，刷新答案为 4。
25往上只返回 max(2, 2) = 2结算完，它要回到父亲那一层。注意往上只能交一条臂，因为路径到了父亲不能在这里分叉，所以返回左右臂里更长的那条 = 2。本节点变绿，结束。
26答案 = 4 条边所有节点都结算完了。全局最长的「经过点」路径是紫色这条 50-50-50-50-50，从左下的 50 经过根再到右下的 50，正好 4 条边。那个 90 跟周围不同值，谁也接不上它，被排除在外。这就是答案。

⚠️ 容易写错的地方

✗ 错：返回时把左臂 + 右臂一起交给父亲

✓ 对：只能返回 max(左臂, 右臂)

路径到父亲不能在本节点分叉，交两条会让父亲算出不存在的路径

✗ 错：答案直接用返回值

✓ 对：答案要用「左臂 + 右臂」单独刷新

最长路径可能在本节点拐弯，跨左右，而返回值只是单边

✗ 错：数成了节点数

✓ 对：答案是边数 = 节点数减一

题目要的是路径长度（边数），5 个同值点是 4 条边

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from 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 = right
class 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 = right
class 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
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) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * 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 longestUnivaluePath(TreeNode* root) {
        int ans = 0;
        function<int(TreeNode*)> dfs = [&]( TreeNode* root ) -> int {
            if (!root) {
                return 0;
            }
            int l = dfs(root->left);
            int r = dfs(root->right);
            l = root->left && root->left->val == root->val ? l + 1 : 0;
            r = root->right && root->right->val == root->val ? r + 1 : 0;
            ans = max(ans, l + r);
            return max(l, r);
        };
        dfs(root);
        return ans;
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private int ans;

    public int longestUnivaluePath(TreeNode root) {
        ans = 0;
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int l = dfs(root.left);
        int r = dfs(root.right);
        l = root.left != null && root.left.val == root.val ? l + 1 : 0;
        r = root.right != null && root.right.val == root.val ? r + 1 : 0;
        ans = Math.max(ans, l + r);
        return Math.max(l, r);
    }
}

复杂度

时间

O(n)

每个节点只被后序访问并结算一次，常数次比较与加法

空间

O(h)

递归栈深 = 树高 h；最坏退化成链时 O(n)，平衡时 O(log n)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着最长同值路径的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

这题和「二叉树的直径」LeetCode 543 有什么关系？+

骨架完全一样，都是后序 DFS、每点用「左加右」更新答案、向上返回更长单臂。区别只在条件:直径每条边都计入，本题只有孩子与父亲同值时这条边才计入，不同值就把对应臂清零。把 543 的无条件累加换成「同值才加一」就变成了 687。

为什么不能在递归里直接返回左臂加右臂？+

因为返回值是给父亲继续往上接的，路径从父亲下来只能走进当前节点的一条孩子方向，不能在当前节点又拐向另一条孩子，那样就不是一条简单路径了。所以返回必须是单臂；而「左加右」这种拐弯路径在当前节点已经是终点，只能用来刷新全局答案。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把最长同值路径一步步讲透（全站 0 节语音精讲，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 687中等树 · BST

最长同值路径图解题解

这道题到底在问什么

给定二叉树 root，求一条路径，路径上每个节点的值都相等，返回这条路径的边数（不是节点数）。路径可经过也可不经过根节点。

输入: root=[5,4,5,1,1,5]
输出: 2
输入: root=[50,50,50,90,50,null,50]（本帧这棵）
输出: 4

最优解：一步一步想明白

3记死这句：经过点取左臂加右臂刷答案，往上只返回更长的单臂。后面每帧都在套它。
4从根下探，叶子先结算先看清这棵树。根是 50，左右孩子也都是 50，只有左下角那个 90 跟大家不一样。后序 DFS 会一路下探到叶子，从最底下往上、一个个把节点结算掉。紫色是正在处理的节点，结算完会变绿。
5处理 idx 0下探到值为 50 的这个节点（紫色）。它还有孩子，得先把左右孩子递归算完，才能轮到它。
6处理 idx 1下探到值为 50 的这个节点（紫色）。它还有孩子，得先把左右孩子递归算完，才能轮到它。
7处理 idx 3下探到值为 90 的这个节点（紫色）。它没有孩子，是叶子，可以直接结算。
8idx 3 臂长 0叶子 90 向下一条边都没有，所以它给父亲的单臂长度是 0。它结算完毕，变绿。
9处理 idx 4下探到值为 50 的这个节点（紫色）。它没有孩子，是叶子，可以直接结算。
10idx 4 臂长 0叶子 50 向下一条边都没有，所以它给父亲的单臂长度是 0。它结算完毕，变绿。
11不同 → 左臂 0看左孩子，它的值是 90，跟当前的 50 不一样，这条边断掉，标红。所以左臂只能归零。
12同值 → 右臂 1再看右孩子，值同样是 50，同值，边接得上。右臂 = 右孩子返回的 0 加一条边 = 1。
13刷新答案 ans = 1把左臂 0 和右臂 1 拼起来，就是经过这个节点的最长同值路径，共 1 条边（紫路径）。它比之前的 ans 大，刷新答案为 1。
14往上只返回 max(0, 1) = 1结算完，它要回到父亲那一层。注意往上只能交一条臂，因为路径到了父亲不能在这里分叉，所以返回左右臂里更长的那条 = 1。本节点变绿，结束。
15处理 idx 2下探到值为 50 的这个节点（紫色）。它还有孩子，得先把左右孩子递归算完，才能轮到它。
16处理 idx 6下探到值为 50 的这个节点（紫色）。它没有孩子，是叶子，可以直接结算。
17idx 6 臂长 0叶子 50 向下一条边都没有，所以它给父亲的单臂长度是 0。它结算完毕，变绿。
18左臂 0当前节点没有左孩子，左边没有可延伸的臂，左臂记 0。
19同值 → 右臂 1再看右孩子，值同样是 50，同值，边接得上。右臂 = 右孩子返回的 0 加一条边 = 1。
20不超过 ans = 1把左臂 0 和右臂 1 拼起来，就是经过这个节点的最长同值路径，共 1 条边（紫路径）。它没超过已有的 ans = 1，答案保持不变。
21往上只返回 max(0, 1) = 1结算完，它要回到父亲那一层。注意往上只能交一条臂，因为路径到了父亲不能在这里分叉，所以返回左右臂里更长的那条 = 1。本节点变绿，结束。
22同值 → 左臂 2看左孩子，它的值也是 50，跟当前节点同值，这条边接得上。于是左臂 = 左孩子返回的 1 再加这一条边 = 2。左孩子标成路径色。
23同值 → 右臂 2再看右孩子，值同样是 50，同值，边接得上。右臂 = 右孩子返回的 1 加一条边 = 2。
24刷新答案 ans = 4把左臂 2 和右臂 2 拼起来，就是经过这个节点的最长同值路径，共 4 条边（紫路径）。它比之前的 ans 大，刷新答案为 4。
25往上只返回 max(2, 2) = 2结算完，它要回到父亲那一层。注意往上只能交一条臂，因为路径到了父亲不能在这里分叉，所以返回左右臂里更长的那条 = 2。本节点变绿，结束。
26答案 = 4 条边所有节点都结算完了。全局最长的「经过点」路径是紫色这条 50-50-50-50-50，从左下的 50 经过根再到右下的 50，正好 4 条边。那个 90 跟周围不同值，谁也接不上它，被排除在外。这就是答案。

⚠️ 容易写错的地方

✗ 错：返回时把左臂 + 右臂一起交给父亲

✓ 对：只能返回 max(左臂, 右臂)

路径到父亲不能在本节点分叉，交两条会让父亲算出不存在的路径

✗ 错：答案直接用返回值

✓ 对：答案要用「左臂 + 右臂」单独刷新

最长路径可能在本节点拐弯，跨左右，而返回值只是单边

✗ 错：数成了节点数

✓ 对：答案是边数 = 节点数减一

题目要的是路径长度（边数），5 个同值点是 4 条边

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from 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 = right
class 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 = right
class 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
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) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * 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 longestUnivaluePath(TreeNode* root) {
        int ans = 0;
        function<int(TreeNode*)> dfs = [&]( TreeNode* root ) -> int {
            if (!root) {
                return 0;
            }
            int l = dfs(root->left);
            int r = dfs(root->right);
            l = root->left && root->left->val == root->val ? l + 1 : 0;
            r = root->right && root->right->val == root->val ? r + 1 : 0;
            ans = max(ans, l + r);
            return max(l, r);
        };
        dfs(root);
        return ans;
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private int ans;

    public int longestUnivaluePath(TreeNode root) {
        ans = 0;
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int l = dfs(root.left);
        int r = dfs(root.right);
        l = root.left != null && root.left.val == root.val ? l + 1 : 0;
        r = root.right != null && root.right.val == root.val ? r + 1 : 0;
        ans = Math.max(ans, l + r);
        return Math.max(l, r);
    }
}

复杂度

时间

O(n)

每个节点只被后序访问并结算一次，常数次比较与加法

空间

O(h)

递归栈深 = 树高 h；最坏退化成链时 O(n)，平衡时 O(log n)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着最长同值路径的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

这题和「二叉树的直径」LeetCode 543 有什么关系？+

为什么不能在递归里直接返回左臂加右臂？+

想听吴师兄把这道题讲给你听？

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

最长同值路径 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

最长同值路径 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

最长同值路径图解题解

最长同值路径图解题解