Alternating-Color Binary Tree Roots
Learn this problem
GoogleFULLTIMEONSITE INTERVIEWProblem statement
You are given a connected undirected tree with nodes numbered from 0 through n - 1. The array edges contains its undirected edges, and colors[i] is either B or W for node i.
A node is a valid root when rooting the tree there satisfies both conditions:
- Every node has at most two children.
- All nodes at the same depth have the same color, and adjacent depths alternate between
BandW.
Return every valid root in increasing node order.
Interview follow-up
The interviewer also asked for the minimum number of node-color changes needed to make the conditions achievable. That follow-up is not part of this function's return value.
Function
findAlternatingBinaryRoots(n: int, edges: int[][], colors: String) → int[]Examples
Example 1
n = 5edges = [[0,1],[1,2],[1,3],[3,4]]colors = "BWBWW"return = []Nodes 3 and 4 have the same color even though they are adjacent, so no root can make every adjacent level alternate.
Example 2
n = 5edges = [[0,1],[1,2],[1,3],[3,4]]colors = "BWBBW"return = [0,2,3,4]Every edge joins different colors. Node 1 has degree 3, so it would have three children if chosen as the root. Every other node has degree at most 2 and is a valid root.
Example 3
n = 4edges = [[0,1],[0,2],[0,3]]colors = "BWWW"return = [1,2,3]Any leaf can be the root: the center then has two children. The center itself is invalid because it would have three children.
Constraints
1 <= n <= 200000edges.length == n - 1- Each edge contains two distinct node indices in
[0, n - 1]. - The edges form one connected acyclic graph.
colors.length == n, and every character isBorW.