这次 6sense 面试主要考了两道 tree 相关题，一道偏工程建模，一道偏递归算法。

题目一：Print Org Chart

原题给了一个员工表：

ID | Name    | Manager ID
1  | Eric    | NULL
2  | Jack    | 1
3  | Viral   | 2
4  | Michael | 2
5  | Nitesh  | 1
6  | George  | 4
7  | Ryan    | 2

员工对象大概是：

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

要求输入一个 Emp list，打印出组织架构：

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

这题核心不是直接打印，而是先把扁平的员工列表还原成一棵树。Manager ID 就是父节点，Manager ID = NULL 的人是 root。

面试时可以先确认：

Can I assume there is only one root employee?
Can the input list be unordered?
Should employees under the same manager preserve input order?

解法很直接：先建一个 managerId -> children list 的 map，同时找到 root。然后从 root 开始 DFS 打印。每深入一层，前面多加一层缩进。

时间复杂度是 O(n)，因为每个员工只处理一次。空间复杂度也是 O(n)，主要用于 hashmap 和 children list。

题目二：Unival Tree

英文题目大意：

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

Part 1: Validate if a given tree is a unival tree.
Part 2: Count the number of unival subtrees.

中文意思是：如果一棵树里所有节点的值都一样，这棵树就是 unival tree。

Part 1：判断整棵树是不是 Unival Tree

这个部分比较简单。

拿 root 的值作为标准值，然后 DFS 遍历整棵树。只要发现某个节点的值和 root 不一样，就返回 false。全部遍历完都一样，就返回 true。

面试里可以这样解释：

I will use the root value as the expected value, then traverse the whole tree. If any node has a different value, the tree is not unival.

时间复杂度 O(n)，递归栈空间 O(h)。

Part 2：统计 Unival Subtrees

这一问是重点。

一个 subtree 是否是 unival，需要满足两个条件：

1. 所有 child subtree 本身都是 unival。
2. 所有 child 的值都等于当前节点的值。

所以要用 post-order DFS。递归函数返回：

当前节点为根的 subtree 是否是 unival

处理每个节点时，先递归处理所有 children。如果所有 child subtree 都是 unival，并且所有 child.val 都等于 node.val，那么当前 subtree 也是 unival，答案加一。

面试中可以这样说：

For each node, the recursive function returns whether the subtree rooted at this node is unival. If all children are unival and all child values equal the current node value, then this subtree is unival and I increment the count.

叶子节点一定是 unival subtree，因为单个节点天然满足条件。

这题常见错误是只比较 child.val == node.val。这不够，因为 child 下面可能还有不同值。必须同时确认 child subtree 自己也是 unival。

例如：

    1
   /
  1
 /
2

root 和 child 都是 1，但整棵 subtree 不是 unival，因为下面还有 2。

复杂度

假设树里有 n 个节点。

每个节点只访问一次，所以时间复杂度是：

O(n)

递归栈取决于树高：

O(h)

最坏情况下树退化成链表，空间复杂度是 O(n)。

csoahelp 面试辅助总结

这次 6sense 的题目难度不算高，但很考察候选人能不能把问题讲清楚。

第一题关键是把 Emp list 转成树，再 DFS 打印。第二题关键是用 post-order DFS，让每个节点返回“当前 subtree 是否 unival”，同时累计数量。

我们在辅助时会让候选人先用英文讲清楚递归返回值、判断条件和复杂度，再开始写代码。这样即使代码还没完全写完，面试官也能确认思路是正确的。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~