2246. Longest Path With Different Adjacent Characters Hard
You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0
consisting of n
nodes numbered from 0
to n - 1
. The tree is represented by a 0-indexed array parent
of size n
, where parent[i]
is the parent of node i
. Since node 0
is the root, parent[0] == -1
.
You are also given a string s
of length n
, where s[i]
is the character assigned to node i
.
Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them.
Example 1:
![](https://assets.leetcode.com/uploads/2022/03/25/testingdrawio.png)
Input: parent = [-1,0,0,1,1,2], s = "abacbe" Output: 3 Explanation: The longest path where each two adjacent nodes have different characters in the tree is the path: 0 -> 1 -> 3. The length of this path is 3, so 3 is returned. It can be proven that there is no longer path that satisfies the conditions.
Example 2:
![](https://assets.leetcode.com/uploads/2022/03/25/graph2drawio.png)
Input: parent = [-1,0,0,0], s = "aabc" Output: 3 Explanation: The longest path where each two adjacent nodes have different characters is the path: 2 -> 0 -> 3. The length of this path is 3, so 3 is returned.
Constraints:
n == parent.length == s.length
1 <= n <= 105
0 <= parent[i] <= n - 1
for alli >= 1
parent[0] == -1
parent
represents a valid tree.s
consists of only lowercase English letters.
class Solution { private int max = 1; public int longestPath(int[] parent, String s) { //build tree, from parent to child List<Integer>[] tree = new List[parent.length]; for(int i = 0; i < parent.length; i++) { if(parent[i] == -1) continue; if(tree[parent[i]] == null) { tree[parent[i]] = new ArrayList(); } tree[parent[i]].add(i); } //dfs dfs(tree, 0, s); //return result return max; } /** * input: tree, current node, string * return: curr node's single longest path */ private int dfs(List<Integer>[] tree, int root, String s){ if(tree[root] == null) return 1; int currmax = 0; //used to store all the result of each child List<Integer> list = new ArrayList(); for(int child : tree[root]){ int curr = dfs(tree, child, s); if(s.charAt(child) != s.charAt(root)) list.add(curr); else list.add(0); } Collections.sort(list, (x, y) -> y-x); max = Math.max(list.get(0) + (list.size() <= 1 ? 0 : list.get(1) ) + 1, max); return list.get(0) + 1; } }
相关题目后续补充:
543.Diameter-of-Binary-Tree (M)
124.Binary-Tree-Maximum-Path-Sum (M)
687.Longest-Univalue-Path (M+)
1522.Diameter-of-N-Ary-Tree (M)
2049.Count-Nodes-With-the-Highest-Score (M+)