Sense OA 面试真题解析：N 叉树的判定与单值子树计数

Part 1: Validate if a given tree is a unival tree.

Part 2: Count the number of unival subtrees.

A unival tree is an n-ary tree in which all nodes have the same value.

Examples:

This is a valid unival tree:

1

This is not:

1
  1
    1 1 2
      1 1

This has 8 unival subtrees:

1
/ \
2   3
/ \ / \
2 2 3 3
/ \ / \ / \
5 5 4 4 3 3

Emp => {id: int, name: string, mid: int}

Write a function which takes input as a list of Emp(s), prints out the org chart as follows:

Eric
|__ Jack
|   |__ Viral
|   |__ Michael
|       |__ George
|   |__ Ryan
|__ Nitesh

这道题其实包含两个经典树问题：第一部分判断一棵 N 叉树是否为 unival tree，也就是整棵树所有节点值都相同；第二部分统计所有单值子树的数量。常见做法是用 DFS/ 后序遍历，自底向上返回当前子树是否满足单值条件，同时在遍历过程中累加满足条件的子树个数。判断时需要把当前节点与所有子节点进行比较，只有当所有子树也都满足并且子节点值与当前节点一致，当前子树才是 unival。组织结构图那一问则是把 id / mid 的员工关系构造成树，再按层级递归或 DFS 格式化输出。