题目重点：根最多两孩子，其余点扣掉父亲后最多两孩子，再检查每层同色。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入是非空无向树，n−1条无重复边且连通；非树输入拒绝，不把森林当一种根。
- 二叉只指孩子数≤2，不要求有序BST或满二叉。颜色follow-up训练为任意标签、同层全相同。
解题路线
- 任意非根点children=degree−1，因此所有degree≤3是必要条件；候选root degree≤2。若满足，这些候选对纯二叉约束全部可行。
- 加颜色后对每个候选root BFS，按depth保存该层第一个颜色，发现另一颜色则拒绝；不得用只检查邻居颜色代替整层比较。
- 输出所有合法root便于明确唯一性；若只要任一个可提前终止。基础颜色重算最坏二次，不能因原图是树就声称所有root检查线性。
手动走一遍
4节点星中心deg3：中心不能作为二叉根，但任一叶可以，中心成为非根后只有两孩子。颜色星形两叶白一叶黑、中心白：选择某叶作根后剩两叶若色不同则该候选失败，具体看层而非边。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
def valid_roots(n,edges,colors=None):
if n<=0 or len(edges)!=n-1:raise ValueError("nonempty undirected tree required")
graph=[set() for _ in range(n)]
for u,v in edges:
if not 0<=u<n or not 0<=v<n or u==v or v in graph[u]:raise ValueError("invalid edge")
graph[u].add(v);graph[v].add(u)
seen={0};todo=[0]
for u in todo:
for v in graph[u]:
if v not in seen:seen.add(v);todo.append(v)
if len(seen)!=n:raise ValueError("disconnected")
if colors is not None and len(colors)!=n:raise ValueError("one color per node required")
if any(len(ns)>3 for ns in graph):return []
result=[]
for root in range(n):
if len(graph[root])>2:continue
if colors is not None:
q=deque([(root,-1,0)]);level={};ok=True
while q:
u,parent,depth=q.popleft()
if depth in level and level[depth]!=colors[u]:ok=False;break
level[depth]=colors[u]
for v in graph[u]:
if v!=parent:q.append((v,u,depth+1))
if not ok:continue
result.append(root)
return result
复杂度
纯度数条件O(n)，带颜色基线O(n²)时间/O(n)空间。输出候选O(n)；树校验同样O(n)。
易错点与追问
容易失分的边界
- degree3不代表一定非法，只有当其作为root才有3孩子。
- 每层同色不要求相邻层不同色，不能误写成二分染色。
继续深挖
- 多次颜色更新如何复用树距离结构？
- 限定完整/满二叉树时哪些额外条件需要检查？
