员工的重要性

记住两句：先建哈希表凭编号秒查到人；再用深度优先，自己的重要度加上所有下属子树的重要度。

总览 · 一张组织架构图：先看清这张图。每个圆圈是一名员工，圈里的大数字是他的编号 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)。