题目描述
思路解析
一句话答案：LeetCode 690 员工的重要性：先建哈希表凭编号 O(1) 查到人，再从目标员工 DFS 累加他自己与所有下属子树的重要度，避免反复扫数组，时间 O(n)、空间 O(n)。
给一个编号，到底要把哪些人的重要度加起来
每名员工带三样东西：唯一编号 id、一个重要度、一份直系下属的编号名单。给你一个员工编号，要返回他本人加上手下所有人的重要度总和——注意是所有人，下属的下属、一直往下到最底层都得算进去。题面例子 employees=[[1,5,[2,3]],[2,3,[]],[3,3,[]]]、id=1：1 号自己 5，两个下属 2 号、3 号各 3，合计 5+3+3=11。重要度还可能是负数，范围 -100 到 100。
顺着下属编号找人，为什么会退化成 O(n²)
下属名单里给的是编号，不是员工本身。要拿到 2 号的重要度，得先在 employees 里把 2 号那条记录捞出来。若每次都从头扫一遍数组比对编号，单次查找就是 O(n)，而整棵组织有 n 个人要查，合起来就是 O(n²)。n 到 2000 时，这多出来的一层扫描纯属白费力气。
先建一张编号到人的表，再顺着下属递归
两个动作配合。第一，建一张哈希表，也就是凭编号一步就能查到对应员工的表，键是 id、值是那名员工；建表只需把 employees 扫一遍，之后任何一次「凭编号找人」都降到 O(1)，不再回头扫数组。第二，从目标编号出发做深度优先，即顺着一条下属链一直走到底再回头：处理一个人时，先取他自己的重要度，再对他名单里的每个下属编号递归求和，两部分相加就是这个人连同整棵下属子树的总重要度。
每个节点返回的到底是什么
把递归看成一个约定：dfs(x) 交回来的，是编号 x 这个人加上他底下所有人的重要度之和。落到代码里就一行——先用哈希表查到 x 本人拿到 importance，再对他每个下属 y 调用 dfs(y)、把这些子树和累加上去。递归自然会往下钻：算 x 得先算清每个下属子树，而下属子树又要先算清它们各自的下属，一层套一层，直到碰上没有下属的人直接返回自身重要度，回程时这些值层层相加汇总回来。这样「下属的下属也要算」根本不用特意处理，递归结构本身就保证不漏人。
拿题面这三名员工顺着算下来
从 dfs(1) 起。哈希表查到 1 号重要度 5，他的下属是 2 号和 3 号，于是要算 5 + dfs(2) + dfs(3)。先看 dfs(2)：2 号重要度 3，下属名单是空的，没有人可再递归，直接返回 3。dfs(3) 同理，3 号重要度 3、名单也空，返回 3。回到 1 号这层，把三块拼起来：5 + 3 + 3 = 11，这就是 1 号的总重要度。
O(n) 之外，三种边界别想当然
建表扫一遍是 O(n)，深度优先里每个相关员工只被查到、累加一次，所有下属编号总共也只走一遍，合起来时间 O(n)；哈希表存下全部 n 个人是 O(n)，递归调用栈在组织链排成一条直线时最深也到 O(n)，空间同样 O(n)。
最常见的错是只把直系下属加进去、漏了下属的下属，题目要的是整棵子树，少算孙辈就丢掉一大片。其次是拿编号直接当数组下标取人，可编号既不连续、最大能到 2000，当下标既浪费又会越界，只能走哈希表。还有人以为重要度都是正的，就跳过或取绝对值，实际它能低到 -100，照常加减才对。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住两句：先建哈希表凭编号秒查到人；再用深度优先，自己的重要度加上所有下属子树的重要度。
总览 · 一张组织架构图：先看清这张图。每个圆圈是一名员工，圈里的大数字是他的编号 id，旁边的小数字是他的重要度。11 号是大老板，他带着 23 号和 37 号两个直系下属；23 号自己又带 42 号和 56 号，37 号带一个 68 号，最下面这三位没有下属。题目要的是从 11 号出发，把他自己加上手下所有人，一层一层全部算到底的重要度总和。提前剧透一下，这个答案是 39，下面我们一步一步把它累出来。
建哈希表 · 编号查得到人：动手之前有一个关键准备。下属在数据里只给了编号，比如 11 号手下是 23 号和 37 号，光有编号还不够，我们得能凭编号立刻找到那个人的重要度和他自己的下属名单。注意这些编号是 11、23、37 这种不连续的数，不能拿编号直接当数组下标去取。所以先扫一遍所有员工，建一张哈希表，把每个编号映射到对应的员工记录。建好之后，无论手里拿到哪个编号，一步就能查到人，这一步是 O(1)，整张表建好是 O(n)。
入栈 · 从 11 号起步：正式开始遍历。我们用一个栈来模拟深度优先搜索，把起点 11 号压进栈，累计总和先记为 0。盯住右边两块面板：上面是待访问员工栈，栈顶在最上面，是下一个要处理的人；下面是已经累加进答案的重要度序列。接下来只重复一个动作：弹出栈顶、查到这个人、把他的重要度加进总和、再把他的直系下属压回栈，直到栈空。
看栈顶 · 11 号：栈里现在只有 11 号，他就是栈顶。深度优先搜索的第一步永远是处理起点自己，所以下一帧把他弹出来累加。
累加 · 11 号：弹出栈顶 11 号，凭编号在哈希表里查到他，重要度是 5，加进总和。累计从 0 变成 5。处理完一个人，紧接着要把他的直系下属安排上。
下属入栈 · 11 号：11 号有两个直系下属 23 号和 37 号，把他们压回栈。这里有个讲究：逆序压，先压右边的 37 号、再压左边的 23 号，这样栈顶就是 23 号，后面会先把 23 号这一整支彻底走完，再回头处理 37 号。11 号自己已结算，变绿。
看栈顶 · 23 号：现在栈顶是 23 号，37 号在他下面排队等着。深度优先的意思就是先一头扎到底，把 23 号这一支连同他的下属全部走完，才轮到 37 号。
累加 · 23 号：弹出 23 号，哈希表查到他重要度 8，加进总和，累计从 5 变成 13。23 号手下还有人，继续安排他的下属。
下属入栈 · 23 号：23 号带着 42 号和 56 号两个下属，同样逆序压栈：先压 56 号、再压 42 号，于是栈顶变成 42 号。此刻栈里从顶到底是 42 号、56 号、37 号，正好等着按这个顺序处理。23 号结算变绿。
看栈顶 · 42 号：栈顶是 42 号，他是 23 号的第一个下属。
累加 · 42 号：弹出 42 号，重要度 4 加进总和，累计从 13 变成 17。
结算 · 42 号无下属：42 号手下没有任何人，是棵子树的叶子，他这一支到此为止，直接结算，节点变绿。
看栈顶 · 56 号：栈顶轮到 56 号，他是 23 号的第二个下属。
累加 · 56 号：弹出 56 号，重要度 7 加进总和，累计从 17 变成 24。到这里，23 号手下的两个人 42 号、56 号都算过了。
结算 · 56 号无下属：56 号也没有下属，结算变绿。23 号这一整支就彻底走完了，现在回头处理一直在栈底等着的 37 号。
看栈顶 · 37 号：栈顶现在是 37 号，他是大老板 11 号的第二个直系下属，刚才一直在栈底耐心排队。
累加 · 37 号：弹出 37 号，重要度 6 加进总和，累计从 24 变成 30。37 号手下还有人，继续安排。
下属入栈 · 37 号：37 号只有一个下属 68 号，把他压回栈，栈顶变成 68 号。37 号结算变绿。
看栈顶 · 68 号：栈里只剩 68 号，他是 37 号唯一的下属，也是整张图最后一个没处理的人。
累加 · 68 号：弹出 68 号，重要度 9 加进总和，累计从 30 变成 39。这时栈空了。
结算 · 68 号无下属：68 号没有下属，结算变绿。栈已经清空，整趟深度优先搜索到此结束。
完成 · 总重要度：所有人都处理过了，全部变绿。看累计总和，正好是 39。我们把它拆开验证一遍：大老板 11 号自己 5，加上 23 号那一支的 8 加 4 加 7 等于 19，再加上 37 号那一支的 6 加 9 等于 15，合起来 5 加 19 加 15 就是 39。整个过程靠一张哈希表凭编号秒查到人，再用深度优先一路扎到底逐个累加，每个人只走一遍，干净利落。
边界想清楚：单个员工返回自身；目标是叶子时就是它自己；重要度为负也正常算。
面试重点：DFS、BFS 都行因为只求总和；哈希表把查找从 O(n) 降到 O(1)。
参考代码
from typing import Listclass Employee: def __init__(self, id: int, importance: int, subordinates: List[int]): self.id = id self.importance = importance self.subordinates = subordinatesclass Solution: def getImportance(self, employees: List['Employee'], id: int) -> int: mp = {e.id: e for e in employees} def dfs(x): e = mp[x] return e.importance + sum(dfs(y) for y in e.subordinates) return dfs(id)复杂度
- 时间：O(n)，建哈希表扫一遍所有员工是 O(n)；深度优先从目标出发，每个相关员工只被访问、累加一次，所有下属指针总共也只走一遍，n 是员工总数
- 空间：O(n)，哈希表存下全部 n 个员工是 O(n)；动画用的显式栈、或递归写法的调用栈，最坏(组织链是一条直线)深度也到 O(n)
易错点
面试追问把动画讲成自己的话
追问这题用 DFS 还是 BFS，有区别吗？
追问为什么非得先建哈希表，不建行不行？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉树剪枝
LeetCode 814 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题