What is the main strategy for Longest Path With Different Adjacent Characters?

Use DFS from the root to track longest paths per subtree, combining branches while ensuring adjacent characters differ.

Why is topological reasoning important in this problem?

It ensures nodes are processed from leaves to root correctly, capturing the longest path contributions from all children.

How do I handle adjacent nodes with the same character?

Exclude paths where the child character matches the current node when calculating maximum path lengths.

What is the time complexity for this tree path problem?

O(n) because each node is visited once in DFS and adjacency list construction is linear.

Can GhostInterview help me debug path calculations for example inputs?

Yes, it walks through sample trees step by step, verifying branch combinations and maximum path updates efficiently.

#2246

Hard

auto_awesome图·搜索

LeetCode 题解工作台

相邻字符不同的最长路径

给你一棵树（即一个连通、无向、无环图），根节点是节点 0 ，这棵树由编号从 0 到 n - 1 的 n 个节点组成。用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树，其中 parent[i] 是节点 i 的父节点，由于节点 0 是根节点，所以 parent[0] == -1 。…

数组字符串树深度优先搜索图

题目描述

给你一棵树（即一个连通、无向、无环图），根节点是节点 0 ，这棵树由编号从 0 到 n - 1 的 n 个节点组成。用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树，其中 parent[i] 是节点 i 的父节点，由于节点 0 是根节点，所以 parent[0] == -1 。

另给你一个字符串 s ，长度也是 n ，其中 s[i] 表示分配给节点 i 的字符。

请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径 ，并返回该路径的长度。

示例 1：

输入：parent = [-1,0,0,1,1,2], s = "abacbe"
输出：3
解释：任意一对相邻节点字符都不同的最长路径是：0 -> 1 -> 3 。该路径的长度是 3 ，所以返回 3 。
可以证明不存在满足上述条件且比 3 更长的路径。

示例 2：

输入：parent = [-1,0,0,0], s = "aabc"
输出：3
解释：任意一对相邻节点字符都不同的最长路径是：2 -> 0 -> 3 。该路径的长度为 3 ，所以返回 3 。

提示：

n == parent.length == s.length
1 <= n <= 10⁵
对所有 i >= 1 ，0 <= parent[i] <= n - 1 均成立
parent[0] == -1
parent 表示一棵有效的树
s 仅由小写英文字母组成

lightbulb

解题思路

方法一：树形 DP

我们先根据数组 $parent$ 构建邻接表 $g$ ，其中 $g[i]$ 表示节点 $i$ 的所有子节点。

然后我们从根节点开始 DFS，对于每个节点 $i$ ，我们遍历 $g[i]$ 中的每个子节点 $j$ ，如果 $s[i] \neq s[j]$ ，那么我们就可以从 $i$ 节点出发，经过 $j$ 节点，到达某个叶子节点，这条路径的长度为 $x = 1 + dfs(j)$ ，我们用 $mx$ 记录最长的一条从节点 $i$ 出发的路径长度。同时，在遍历的过程中，更新答案 $ans = \max(ans, mx + x)$ 。

最后，我们返回 $ans + 1$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为节点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        def dfs(i: int) -> int:
            mx = 0
            nonlocal ans
            for j in g[i]:
                x = dfs(j) + 1
                if s[i] != s[j]:
                    ans = max(ans, mx + x)
                    mx = max(mx, x)
            return mx

        g = defaultdict(list)
        for i in range(1, len(parent)):
            g[parent[i]].append(i)
        ans = 0
        dfs(0)
        return ans + 1

speed

复杂度分析

指标	值
时间	complexity is O(n) because each node is visited once during DFS. Space complexity is O(n) for the adjacency list and recursion stack. The approach scales linearly with tree size, avoiding redundant traversal of nodes or subtrees.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on graph indegree plus topological ordering.
question_mark
Watch for combining two longest child paths at each node.
question_mark
Verify edge cases where characters repeat consecutively along branches.

warning

常见陷阱

外企场景

error
Counting paths with repeated adjacent characters.
error
Ignoring second-longest child when combining paths through a node.
error
Mismanaging recursion stack leading to excessive memory use.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the longest path where adjacent nodes differ by at least k characters in a string.
arrow_right_alt
Compute the longest path in a k-ary tree with unique node labels.
arrow_right_alt
Determine the maximum path length avoiding a specified subset of characters.

help

常见问题

外企场景

继续练习

#2328 网格图中递增路径的数目 #2368 受限条件下可到达节点的数目 #2115 从给定原材料中找到所有可以做出的菜