admin 管理员组

文章数量: 1086019

【Leetcode】2246. Longest Path With Different Adjacent Characters

题目地址：

/

给定一棵 n n n个节点的有根树，每个节点的编号 0 ∼ n − 1 0\sim n-1 0∼n−1，并且每个节点 i i i对应一个字符 s [ i ] s[i] s[i]。问树中最长的相邻节点字符不同的路径长度。

枚举路径最高节点，递归求所有当前节点儿子出发向下的最长路径长度，求出不同于当前节点字符的儿子的最长路径前两名，那么也就求出了最高节点为当前节点的最长路径长度。枚举完所有最高点之后即得答案。代码如下：

import java.util.ArrayList;
import java.util.List;public class Solution {int res;public int longestPath(int[] parent, String s) {int n = parent.length;List<Integer>[] g = new ArrayList[n];for (int i = 0; i < n; i++) {g[i] = new ArrayList<>();}for (int i = 1; i < n; i++) {g[parent[i]].add(i);}dfs(0, g, s);return res;}int dfs(int u, List<Integer>[] g, String s) {if (g[u].isEmpty()) {res = Math.max(res, 1);return 1;}int max1 = 0, max2 = 0;for (int ne : g[u]) {int len = dfs(ne, g, s);if (s.charAt(ne) != s.charAt(u)) {if (len > max1) {max2 = max1;max1 = len;} else if (len > max2) {max2 = len;}}}res = Math.max(res, max1 + 1 + max2);return 1 + max1;}
}

时空复杂度 O ( n ) O(n) O(n)。

本文标签： Leetcode2246 Longest Path With Different Adjacent Characters

版权声明：本文标题：【Leetcode】2246. Longest Path With Different Adjacent Characters 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1693585169a230720.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。