题目描述
思路解析
一句话答案：LeetCode 2196 根据描述创建二叉树：哈希表按值建节点、取节点、接边，同一个值全程只留一个实例；根是唯一没当过孩子的值，时间 O(n)、空间 O(n)。
一堆父子描述，怎么拼回原来那棵树
给一个二维数组 descriptions，每条是 [parent, child, isLeft]：isLeft 是 1 表示 child 是 parent 的左孩子，0 是右孩子。各节点值互不相同，让你拼出二叉树、返回根节点。题面例子 descriptions=[[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]，根是 50，层序遍历是 50,20,80,15,17,19。
读一条就新建一个节点，两处会崩
描述是乱序的，没法从根往下顺着建。第一反应是读一条就把两个值各造节点、按 isLeft 接边，但两处会崩：同一个值会反复出现，20 既在 [20,15,1] 当父亲、又在 [50,20,1] 当孩子，重复造新节点会让父子指向不同实例，那半棵就断开；根也不能拿第一条的 parent 当，它其实可能是别人的孩子。
同值只留一个节点，根是没人认领的那个
先解决同值：用哈希表按值存节点，也就是给每个值配一张能直接查到它节点的表。每读到一个值先查表，有就取旧节点复用，没有才新建，同一个值全程只有一个实例。
再解决找根：另开一个 children 集合，凡当过 child 的值都塞进去。所有值里唯一没进这个集合的就是根，它从没被任何描述当成孩子。
一趟扫描接边，末尾用差集挑根
代码就一趟遍历：每条 [parent, child, isLeft]，parent、child 缺谁补建谁，child 记进 children 集合，按 isLeft 让 parent 左或右指针指向 child 节点。扫完拿所有值的集合减去 children，剩下唯一那个值对应的节点就是根。
五条描述走一遍，50 怎么浮出来
拿题面五条逐条过。[20,15,1]：20、15 都新建，20 左指向 15。[20,17,0]：20 复用，17 新建，20 右指向 17。[50,20,1]：50 新建，20 复用，50 左指向 20，20 连着 15、17 挂到 50 底下。[50,80,0]：50 复用，80 新建，50 右指向 80。[80,19,1]：80 复用，19 新建，80 左指向 19。
五条读完，当过孩子的是 {15,17,20,80,19}，出现过的值 {15,17,20,50,80,19} 减掉它只剩 50。50 就是根，从它层序遍历，输出就是 50,20,80,15,17,19。
复用一松手，半棵树就断开
复杂度：设描述 n 条，每条只做常数次哈希操作，建取节点、接边、加值；最后找根遍历所有值。时间 O(n)，哈希表和 children 集合都不超过 2n 量级，空间 O(n)。
几个地方一松手就错。同值第二次出现必须取旧节点，重建一个会让父子指向不同实例，那半棵树当场断开。判根别认第一条的 parent，乱序里它常是别人的孩子。一个值还能既当父又当子：20 是 15、17 的父亲、又是 50 的孩子，照样进集合、照样不是根。单条描述时 parent 就是根。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这两句:哈希表保证同名同节点、乱序也能接对边;孩子集合专门用来挑根。下面从第一条描述开始,一条一条走。
概览 · 先把六个位置摆好：舞台先用淡色把这六个值将来所在的位置摆出来,当作最终形态的参照。此刻哈希表还是空的,一个节点都没真正建。约定颜色:淡色表示还没建,蓝色表示已经进了哈希表,绿色表示这个值当过别人的孩子。下面每读一条描述,该新建的值就会亮起来。
第一条 · 读 [20,15,1] · 备好两个节点：读第一条描述 [20,15,1]。parent 20 和 child 15 都第一次出现,各新建一个节点。现在紫色是父亲 20,橙色是孩子 15。
第一条 · 20.left = 15：isLeft 是 1,把 15 接到 20 的左孩子指针上。看 20 到 15 这条边,归属就定下来了。
第一条 · 把 15 记进孩子集合：15 现在是别人的孩子了,把它记进孩子集合,同时它变成绿色。凡是进了这个集合的值,都不可能是根。目前孩子集合里有 15。
第二条 · 读 [20,17,0] · 备好两个节点：读第二条描述 [20,17,0]。parent 20 已在哈希表里,取出复用;child 17 是新的,新建。现在紫色是父亲 20,橙色是孩子 17。
第二条 · 20.right = 17：isLeft 是 0,把 17 接到 20 的右孩子指针上。看 20 到 17 这条边,归属就定下来了。
第二条 · 把 17 记进孩子集合：17 现在是别人的孩子了,把它记进孩子集合,同时它变成绿色。凡是进了这个集合的值,都不可能是根。目前孩子集合里有 15, 17。
第三条 · 读 [50,20,1] · 备好两个节点：读第三条描述 [50,20,1]。parent 50 是新的,新建;child 20 已在哈希表里,取出复用。现在紫色是父亲 50,橙色是孩子 20。
第三条 · 50.left = 20：isLeft 是 1,把 20 接到 50 的左孩子指针上。看 50 到 20 这条边,归属就定下来了。这一步很关键:20 顶着 15、17 那半棵小树,整个被挂到了主干 50 底下。
第三条 · 把 20 记进孩子集合：20 现在是别人的孩子了,把它记进孩子集合,同时它变成绿色。凡是进了这个集合的值,都不可能是根。目前孩子集合里有 20, 15, 17。
第四条 · 读 [50,80,0] · 备好两个节点：读第四条描述 [50,80,0]。parent 50 已在哈希表里,取出复用;child 80 是新的,新建。现在紫色是父亲 50,橙色是孩子 80。
第四条 · 50.right = 80：isLeft 是 0,把 80 接到 50 的右孩子指针上。看 50 到 80 这条边,归属就定下来了。
第四条 · 把 80 记进孩子集合：80 现在是别人的孩子了,把它记进孩子集合,同时它变成绿色。凡是进了这个集合的值,都不可能是根。目前孩子集合里有 20, 80, 15, 17。
最后一条 · 读 [80,19,1] · 备好两个节点：读最后一条描述 [80,19,1]。parent 80 已在哈希表里,取出复用;child 19 是新的,新建。注意 80 之前作为别人的孩子已经登记过绿色了,这次它换个身份当父亲。现在紫色是父亲 80,橙色是孩子 19。
最后一条 · 80.left = 19：isLeft 是 1,把 19 接到 80 的左孩子指针上。看 80 到 19 这条边,归属就定下来了。到这里,整棵树的边就全接完了。
最后一条 · 把 19 记进孩子集合：19 现在是别人的孩子了,把它记进孩子集合,同时它变成绿色。凡是进了这个集合的值,都不可能是根。目前孩子集合里有 20, 80, 15, 17, 19。
找根 · 谁没当过孩子：五条描述读完,边全接好了。可根是谁?规律只有一条:根是唯一一个从来没当过别人孩子的值。现在孩子集合里是 20, 80, 15, 17, 19,绿色的这五个都当过孩子。只剩蓝色的 50 还没进过集合,拿几个值一个个去对照确认一下。
检查 20 · 在集合里,跳过：20 在孩子集合里,它当过别人的孩子,不是根,跳过看下一个。
检查 15 · 在集合里,跳过：15 在孩子集合里,它当过别人的孩子,不是根,跳过看下一个。
检查 17 · 在集合里,跳过：17 在孩子集合里,它当过别人的孩子,不是根,跳过看下一个。
检查 50 · 不在集合,就是根：轮到 50,它不在孩子集合里。也就是说,没有任何一条描述把 50 当成过孩子,它就是这棵树的根节点。
完成 · 根 = 50：找到根 50,从它出发,这棵树就是答案,层序遍历正好是 50,20,80,15,17,19。回头看整道题其实就两步:用哈希表按值建节点、取节点、接边,保证乱序也接得对;再用孩子集合挑出那个没当过孩子的根。
边界想清:单条描述的 parent 即根;一条链只有链头没当过孩子;有几个孩子不影响根的判定。
面试重点:哈希表解乱序、孩子集合挑根、时间空间都是 O(n),差集与遍历两种找根写法等价。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]: nodes = defaultdict(TreeNode) children = set() for parent, child, isLeft in descriptions: if parent not in nodes: nodes[parent] = TreeNode(parent) if child not in nodes: nodes[child] = TreeNode(child) children.add(child) if isLeft: nodes[parent].left = nodes[child] else: nodes[parent].right = nodes[child] root = (set(nodes.keys()) - children).pop() return nodes[root]复杂度
- 时间：O(n)，n 是描述条数。每条描述做常数次哈希操作:建或取两个节点、接一条边、往集合加一个值;最后遍历所有值找根,值的个数不超过 2n,整体随 n 线性增长
- 空间：O(n)，按峰值算。哈希表最多存约 2n 个节点,因为每条描述最多引入两个新值;children 集合最多 n 个值。二者都是 O(n),不随 n 平方增长
易错点
面试追问把动画讲成自己的话
追问为什么用哈希表按值存节点,而不是按顺序建?
追问怎么找根,复杂度是多少?
追问Python 和 Java、C plus plus 找根写法差在哪?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
统计值等于子树平均值的节点数
LeetCode 2265 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题