题目描述
思路解析动画文字版
记牢这两句:哈希表保证同名同节点、乱序也能接对边;孩子集合专门用来挑根。下面从第一条描述开始,一条一条走。
概览 · 先把六个位置摆好：舞台先用淡色把这六个值将来所在的位置摆出来,当作最终形态的参照。此刻哈希表还是空的,一个节点都没真正建。约定颜色:淡色表示还没建,蓝色表示已经进了哈希表,绿色表示这个值当过别人的孩子。下面每读一条描述,该新建的值就会亮起来。
第一条 · 读 [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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题