You are given a tree rooted at node 0, consisting of n nodes numbered from 0 to n - 1. The tree is represented by an 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.
Consider an empty string dfsStr, and define a recursive function dfs(int x) that takes a node x as a parameter and performs the following steps in order:
Iterate over each child y of xin increasing order of their numbers , and call dfs(y).
Add the character s[x] to the end of the string dfsStr.
Note that dfsStr is shared across all recursive calls of dfs.
You need to find a boolean array answer of size n, where for each index i from 0 to n - 1, you do the following:
Empty the string dfsStr and call dfs(i).
If the resulting string dfsStr is a palindrome, then set answer[i] to true. Otherwise, set answer[i] to false.
Input: parent =[-1,0,0,1,1,2], s ="aababa"Output: [true,true,false,true,true,true]Explanation:
* Calling `dfs(0)` results in the string `dfsStr = "abaaba"`, which is a palindrome.* Calling `dfs(1)` results in the string `dfsStr = "aba"`, which is a palindrome.* Calling `dfs(2)` results in the string `dfsStr = "ab"`, which is**not** a palindrome.* Calling `dfs(3)` results in the string `dfsStr = "a"`, which is a palindrome.* Calling `dfs(4)` results in the string `dfsStr = "b"`, which is a palindrome.* Calling `dfs(5)` results in the string `dfsStr = "a"`, which is a palindrome.
The key idea is to simulate the DFS as described, building the string for each subtree rooted at every node, and then check if the resulting string is a palindrome. Since the tree can be large, we need to be careful with string operations, but for each node, we can construct the string by traversing its subtree in postorder.
classSolution {
public List<Boolean>checkPalindromeDFS(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);
for (List<Integer> v : g) Collections.sort(v);
List<Boolean> ans =new ArrayList<>();
for (int i = 0; i < n; i++) {
StringBuilder t =new StringBuilder();
dfs(i, g, s, t);
ans.add(isPalindrome(t));
}
return ans;
}
voiddfs(int u, List<Integer>[] g, String s, StringBuilder t) {
for (int v : g[u]) dfs(v, g, s, t);
t.append(s.charAt(u));
}
booleanisPalindrome(StringBuilder t) {
int l = 0, r = t.length() - 1;
while (l < r) if (t.charAt(l++) != t.charAt(r--)) returnfalse;
returntrue;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
classSolution {
funcheckPalindromeDFS(parent: IntArray, s: String): List<Boolean> {
val n = parent.size
val g = Array(n) { mutableListOf<Int>() }
for (i in1 until n) g[parent[i]].add(i)
g.forEach { it.sort() }
val ans = MutableList(n) { false }
fundfs(u: Int, t: StringBuilder) {
for (v in g[u]) dfs(v, t)
t.append(s[u])
}
for (i in0 until n) {
val t = StringBuilder()
dfs(i, t)
ans[i] = t.toString() == t.reverse().toString()
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution:
defcheck_palindrome_dfs(self, parent: list[int], s: str) -> list[bool]:
n = len(parent)
g: list[list[int]] = [[] for _ in range(n)]
for i in range(1, n):
g[parent[i]].append(i)
for v in g:
v.sort()
defdfs(u: int, t: list[str]):
for v in g[u]:
dfs(v, t)
t.append(s[u])
ans: list[bool] = []
for i in range(n):
t: list[str] = []
dfs(i, t)
ans.append(t == t[::-1])
return ans
⏰ Time complexity: O(n^2), as for each node, we perform a DFS to collect all characters in its subtree, which can take up to O(n) time per node in the worst case (e.g., a skewed tree). Since we do this for every node, the total time is O(n^2).
🧺 Space complexity: O(n^2), as we may construct a string of up to O(n) size for each node, and since we do this for all n nodes, the total auxiliary space can reach O(n^2) in the worst case.