最长同值路径 图解题解

同值路径数的是边，不是节点

给一棵二叉树 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 就整整多出一条。

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);
    }
}