Postorder Palindrome Queries
HardTrees · Google
You are given a tree with n nodes numbered 1 to n, as a list of undirected edges, and a string labels where node v has the character labels[v - 1]. The tree is rooted at node 1.
For a node v, define postorder(v) as the string built by visiting v's subtree in postorder: first build postorder(c) for each child c of v in increasing node-number order and concatenate them, then append v's own label.
For each node in queries, return True if its postorder string is a palindrome (reads the same forwards and backwards) and False otherwise. Return the answers in query order.
Example 1
- Input:
- n = 5, edges = [[1, 2], [1, 3], [2, 4], [2, 5]], labels = "abcba", queries = [2, 1, 3]
- Output:
- [True, False, True]
- Explanation
- Node 2 has children 4 and 5, so postorder visits 4, then 5, then 2, giving
bab. Node 1 givesbabca, since its own label comes last. Node 3 is a leaf, so its string is the singlec.
Example 2
- Input:
- n = 6, edges = [[3, 1], [1, 2], [3, 6], [5, 3], [3, 4]], labels = "aabbab", queries = [3, 1, 2]
- Output:
- [False, False, True]
- Explanation
- Node 3's children are 4, 5 and 6 (sorted), so its string is
b+a+b+ its ownb=babb, not a palindrome. Node 1 visits child 2 (a), then the block for 3, then itself:ababba, also not a palindrome. Leaf 2 alone isa.
Example 3
- Input:
- n = 4, edges = [[1, 2], [2, 3], [3, 4]], labels = "abba", queries = [1, 2, 4]
- Output:
- [True, False, True]
- Explanation
- The tree is a path 1-2-3-4, so node 1 collects the labels bottom up as
abba, a palindrome. Node 2 givesabb, which is not. Node 4 is a leaf,a.
Constraints
1 <= n <= 10^5edges.length == n - 1and the edges form a treelabelshas lengthnand contains lowercase English letters1 <= queries.length <= 10^5, and each query is a node id between1andn