Hard

题目描述

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

另给你一个长度为 n 的字符串 s ，其中 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 仅由小写英文字母组成

解题思路

这道题需要在树中找到相邻字符不同的最长路径。由于是树结构，最长路径必定经过某个节点，该节点可以作为路径的"中心点"。

核心思路是使用深度优先搜索（DFS）：

  1. 从根节点开始DFS遍历整棵树
  2. 对于每个节点，计算从该节点向下延伸的最长路径长度
  3. 考虑以当前节点为"中心"的路径：选择两个最长的子路径进行连接
  4. 在遍历过程中更新全局最长路径

具体实现：

  • 对每个节点，递归计算其所有子节点的最长向下路径
  • 只有当子节点字符与当前节点字符不同时，才能连接路径
  • 选择最长的两条子路径，它们的长度之和+1就是以当前节点为中心的最长路径
  • 向上返回时，只能返回一条最长的子路径长度+1

这种方法确保了每个可能的路径都被考虑到，时间复杂度为O(n)，因为每个节点只访问一次。

代码实现

class Solution {
public:
    int longestPath(vector<int>& parent, string s) {
        int n = parent.size();
        vector<vector<int>> children(n);
        
        // 构建邻接表
        for (int i = 1; i < n; i++) {
            children[parent[i]].push_back(i);
        }
        
        int maxPath = 1;
        
        function<int(int)> dfs = [&](int node) -> int {
            int maxLen1 = 0, maxLen2 = 0;
            
            for (int child : children[node]) {
                int childLen = dfs(child);
                
                // 只有字符不同才能连接
                if (s[child] != s[node]) {
                    if (childLen > maxLen1) {
                        maxLen2 = maxLen1;
                        maxLen1 = childLen;
                    } else if (childLen > maxLen2) {
                        maxLen2 = childLen;
                    }
                }
            }
            
            // 更新全局最长路径
            maxPath = max(maxPath, maxLen1 + maxLen2 + 1);
            
            // 返回从当前节点向下的最长路径
            return maxLen1 + 1;
        };
        
        dfs(0);
        return maxPath;
    }
};

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(parent)
        children = [[] for _ in range(n)]
        
        # 构建邻接表
        for i in range(1, n):
            children[parent[i]].append(i)
        
        self.max_path = 1
        
        def dfs(node):
            max_len1 = max_len2 = 0
            
            for child in children[node]:
                child_len = dfs(child)
                
                # 只有字符不同才能连接
                if s[child] != s[node]:
                    if child_len > max_len1:
                        max_len2 = max_len1
                        max_len1 = child_len
                    elif child_len > max_len2:
                        max_len2 = child_len
            
            # 更新全局最长路径
            self.max_path = max(self.max_path, max_len1 + max_len2 + 1)
            
            # 返回从当前节点向下的最长路径
            return max_len1 + 1
        
        dfs(0)
        return self.max_path

public class Solution {
    private int maxPath = 1;
    
    public int LongestPath(int[] parent, string s) {
        int n = parent.Length;
        List<int>[] children = new List<int>[n];
        
        for (int i = 0; i < n; i++) {
            children[i] = new List<int>();
        }
        
        // 构建邻接表
        for (int i = 1; i < n; i++) {
            children[parent[i]].Add(i);
        }
        
        DFS(0, children, s);
        return maxPath;
    }
    
    private int DFS(int node, List<int>[] children, string s) {
        int maxLen1 = 0, maxLen2 = 0;
        
        foreach (int child in children[node]) {
            int childLen = DFS(child, children, s);
            
            // 只有字符不同才能连接
            if (s[child] != s[node]) {
                if (childLen > maxLen1) {
                    maxLen2 = maxLen1;
                    maxLen1 = childLen;
                } else if (childLen > maxLen2) {
                    maxLen2 = childLen;
                }
            }
        }
        
        // 更新全局最长路径
        maxPath = Math.Max(maxPath, maxLen1 + maxLen2 + 1);
        
        // 返回从当前节点向下的最长路径
        return maxLen1 + 1;
    }
}

var longestPath = function(parent, s) {
    const n = parent.length;
    const children = Array.from({ length: n }, () => []);
    
    // 构建邻接表
    for (let i = 1; i < n; i++) {
        children[parent[i]].push(i);
    }
    
    let maxPath = 1;
    
    function dfs(node) {
        let maxLen1 = 0, maxLen2 = 0;
        
        for (const child of children[node]) {
            const childLen = dfs(child);
            
            // 只有字符不同才能连接
            if (s[child] !== s[node]) {
                if (childLen > maxLen1) {
                    maxLen2 = maxLen1;
                    maxLen1 = childLen;
                } else if (childLen > maxLen2) {
                    maxLen2 = childLen;
                }
            }
        }
        
        // 更新全局最长路径
        maxPath = Math.max(maxPath, maxLen1 + maxLen2 + 1);
        
        // 返回从当前节点向下的最长路径
        return maxLen1 + 1;
    }
    
    dfs(0);
    return maxPath;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n) - 每个节点访问一次
空间复杂度O(n) - 递归栈深度最坏为O(n)，邻接表存储需要O(n)空间

相关题目