二叉树中的链表

记牢两层:外层换起点,内层从起点一路向下比链表。链表先走完就赢;遇到空节点或值对不上就断,回头换方向。下面每一帧都在套这条规则。

总览 · 树 + 链表：先看清两边。左边是树:根是 10,它有两个孩子都是 40;左边那个 40 下面挂 20 和 70,20 再下面挂一个 30;右边那个 40 下面挂 20 和 90,这个 20 下面挂一个 80。右边面板是链表 40 → 20 → 80。我们的任务,就是在树里找一条一直向下的路,值正好按 40、20、80 排下来。

认方向 · 必须一直向下：强调一个容易忽略的点:路径必须一直向下。也就是从某个节点出发,只能顺着父亲到孩子的方向走,不能拐到兄弟,也不能往上回。所以第一步要解决的是:链表的第一个值 40,该从树里哪个节点开始接?那就把每个节点都当起点试一遍。

试起点 · 根 10：从根 10 开始试。链表当前要匹配的是第一个值 40,那就拿它和起点 10 比。规则很直接:起点的值必须等于链表第一个值 40,这条路才有戏。来看 10 和 40 相不相等。

失败 · 10 不等于 40：10 不等于 40,第一步就对不上。既然起点的值都和链表头不一样,这条根本接不起来,直接断掉。外层于是放弃用根当起点,转头去它的孩子里继续找。先去左孩子那个 40。

试起点 · 左边的 40：换根的左孩子,这个 40,当新起点。蓝色的根表示它已经试过、淘汰了。现在拿链表第一个值 40 和这个起点 40 比。这回看着有戏:40 和 40。

匹配 · 40 对上,链表前进到 20：40 等于 40,第一格对上了!这个 40 标成匹配链的一员。链表往前走一格,接下来要匹配的是第二个值 20。按规则,要分别往这个 40 的左孩子和右孩子两个方向继续向下找 20。它的左孩子是 20,右孩子是 70,先看左边。

向下 · 看左孩子 20：走到这个 40 的左孩子,值是 20。链表现在要匹配的也正好是 20。拿它俩比:20 和 20,看起来又能对上。

匹配 · 20 对上,链表前进到 80：20 等于 20,第二格也对上了!现在匹配链已经是 40 → 20,链表只剩最后一个值 80 要找。继续往这个 20 的孩子走。它的左孩子是 30,右孩子是空。先看左孩子 30。

向下 · 看 30：走到这个 20 的左孩子,值是 30。链表现在要匹配的是最后一个值 80。拿 30 和 80 比,这俩差得有点远了。

失败 · 30 不等于 80：30 不等于 80,对不上,这个方向断掉。但别急着否定整条路,这个 20 还有一个右孩子方向没试。来看它的右孩子。

向下 · 右孩子是空：这个 20 的右孩子是空的。树节点都没有了,自然也接不上 80。两个方向都断了,说明从左边这个 40 出发、走到 20 这一支,到第三层就接不上 80 了。那就得往回退,回到那个 40,试它的另一条分支。

回溯 · 回到 40 试右孩子 70：回溯。退回到左边这个 40,它的左孩子那条已经走死,现在试它的右孩子 70。注意链表也跟着退回去:之前在 20 那一格走断了,现在重新从 40 之后的第二个值 20 开始,拿它和 70 比。

失败 · 70 不等于 20,起点 40 走不通：70 不等于 20,这条也断。到此,左边这个 40 当起点的所有向下方向都试完了,全军覆没。不过它是目前最接近的一条:成功接上了 40 和 20 两层,只差最后一个 80 没接上。可惜差一点也是不行。外层只好放弃这个 40,继续换别的节点当起点。

快速跳过 · 首值就不是 40 的起点：外层会老老实实把每个节点都当起点试。但像 20、30、70 这些节点,链表第一个值要的是 40,它们第一步就对不上,试一下立刻就弃,花不了多少功夫。这些蓝色节点表示都淘汰了。真正还没试的关键起点,是根右边那个 40。

试起点 · 右边的 40：轮到根的右孩子,这个 40。前面试过的节点都成蓝色了。和左边那个 40 一样,先拿链表第一个值 40 和它比。又是 40 对 40。

匹配 · 40 对上,链表前进到 20：40 等于 40,第一格又对上,这个 40 进入匹配链。链表前进,要找第二个值 20。看这个 40 的两个孩子:左孩子是 20,右孩子是 90。先看左边的 20。

向下 · 看左孩子 20：走到右边 40 的左孩子,值是 20,链表要找的也是 20。拿它俩比,20 对 20。

匹配 · 20 对上,链表前进到 80：20 等于 20,第二格对上!匹配链现在是 40 → 20,链表只剩最后一个 80。看这个 20 的孩子:左孩子正好是 80,右孩子是空。来看左孩子。

向下 · 看 80：走到这个 20 的左孩子,值是 80。链表最后要匹配的也正是 80。这是决定胜负的一比:80 和 80。

成功 · 80 对上,链表走完：80 等于 80!链表的三个值 40、20、80 全部按顺序对上了。匹配到这里,链表已经走完,后面再没有节点要找了,这正是成功的标志:链表先走完,就说明这条向下的路径完整地装下了整条链表。返回 true。

完成 · 答案 true：收工。绿色的三个节点 40 → 20 → 80,就是树里那条和链表一一对上的向下路径,它在根右边那个 40 的底下。因为找到了这样一条路径,整道题的答案就是 true。

回放 · 两个 40 的对比：最后回放一下最有意思的对比。树里有两个 40,左边那个红色的,匹配上了 40 和 20,可第三层接不上 80,断了;右边那个绿色的,一路 40、20、80 顺顺当当走到底。这正说明:同样的起点值,结果可能完全不同,所以外层要不厌其烦地把每个节点都试一遍,只要有任意一条向下路径成立,答案就是 true。

边界看三种:单值链表只看起点值是否相等;链表比任何向下路径都长就接不完返回 false;别忘了链表走完才算成功。

面试重点:判定顺序要先看链表走完(成功)再看树空或值不等(失败);朴素解有重复可用 KMP 优化到线性;每步必须左右两个孩子都试。