🎮 树根猎人：从一堆父子关系里揪出老祖宗
一只灰扑扑的信鸽扑棱着翅膀从窗口栽了进来，精准地砸中了我刚泡好的方便面。我解开它腿上的字条一看——是村长的笔迹：“邻村要建棵树，你帮忙看看。”
“建树？“我一个刷算法的，什么时候接了土木工程的活儿？这委托费够不够赔我这碗红烧牛肉面！翻到字条背面，还有一整页三元组：[parent, child, isLeft]。我恍然大悟，此树非彼树。邻村要建的是一棵家谱二叉树，但现在只有一堆零散的父子关系——不成树，也不知道根在哪。村长要我根据这些描述把树拼好，并找出根节点。
“清官难断家务事，“我把字条往桌上一拍，露出职业性的微笑，“但算法能解父子局。”
说白了，就是从一堆“谁是谁他爹”的八卦信息里重建完整的家族谱系。我理了理思路，这事分两步走：
第一步：补全亲属关系网
对着家谱名单，把每个人的直系亲属关系一条条补全——把每个节点造出来，顺便把父子指针挂上。这就像是给村里的每个人办身份证，然后记录他们的亲子关系。
第二步：找出老祖宗
那个只当爹、不当娃的根节点，就是我们要找的目标。在任一个三元组的 child 位置上出现的都是娃，而只有老祖宗——那个从来没当过子女的人——永远不会出现在 child 位置上。所以策略很简单：把所有出现过的 child 收集到一个集合里，再遍历所有节点，哪个不在 child 集合里，哪个就是根。
“这不就是玩‘谁是卧底’吗？”我自言自语，“所有人都有爹，就他没有——那他就是老祖宗。”
我搓搓手，开始落代码，先准备两样东西：
- 一个哈希表
nodes：以节点值为 key，存节点对象。这就好比是村里的户口本，每个人都在这里登记。 - 一个集合
children：专门登记所有当过娃的节点，用来筛根。这就是我们的"有爹人士名单”。
nodes = {}
children = set()
接着，遍历 descriptions 里的每一条 [parent, child, isLeft]。对于 parent 和 child，先去 nodes 里查一下：没有就当场 new 一个 TreeNode 塞进去。然后，根据 isLeft 把 child 挂到 parent 左边或右边，父子关系定下来。最后把 child 扔进 children 集合，留个案底，证明这孩子有爹。
for parent, child, is_left in descriptions:
if parent not in nodes:
nodes[parent] = TreeNode(parent)
if child not in nodes:
nodes[child] = TreeNode(child)
if is_left:
nodes[parent].left = nodes[child]
else:
nodes[parent].right = nodes[child]
children.add(child)
遍历跑完，整棵树的骨架就全部搭好了。接下来找根——那个唯一没出现在 children 集合里的人：
for x, node in nodes.items():
if x not in children:
return node
一趟主循环把建节点、挂关系、登记子女全部搞定，最后再来一趟小循环抓老祖。总复杂度 O(n)，线性扫描，丝滑流畅。
村长很快就过来要结果了。他戴着老花镜，眯着眼扫了下代码，点了点头：“哈希表挂节点这种基操就不夸你了——能想到把找根的线索嵌在建节点的同一个循环里，边建边登记，最后差集一把梭，说明你开始有‘数据处理流水线’的意识了。”
他把字条翻了个面，确认背面没有隐藏附加条件，满意地往怀里一揣：“行了，邻村还等着这棵树回去祭祖呢。对了，他们说要感谢你，送了你一袋土豆。”
“……土豆？”
“嗯，说是自家种的，纯天然无污染。”
我看了看桌上那碗被信鸽毁掉的方便面，又想了想这趟委托的收入，叹了口气。算了，至少不是 Bug。
送走村长后，我拆开那袋土豆，发现下面还压着一张小纸条：
“多谢相助。另：如果你愿意帮我们优化一下农田灌溉系统的最短路径算法，报酬是十袋土豆。”
我一把抓起纸条，搓成一团，扔了出去。
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。