LeetCode 1367. 二叉树中的链表

2025-03-20 HGNULB 约 10 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 1367. 二叉树中的链表

题意分析

给一条链表和一棵二叉树，问树里是否存在一条向下的路径，其节点值序列恰好等于链表从头到尾的值序列。

「向下」是全题最关键的限定：路径必须从某个树节点出发，每一步只能走到自己的左孩子或右孩子，不能横向走、不能回头走父节点。所以候选路径的形状是唯一确定的——起点定了之后，每一步只有两个方向可选。

起点没有任何限制，不必是根节点，也不必走到叶子节点。链表可以在树的中途结束，只要值序列对上就算成功。这两点合起来说明：起点要枚举，终点不用枚举。

另一个容易忽略的信息是，比较的只是节点的值，不是结构。链表是一条线，树的路径也是一条线，两者只在数值上对齐即可。

约束规模是树最多 2500 个节点、链表最多 100 个节点，节点值范围 [1, 100]。$2500 \times 100 = 25$ 万次比较，说明出题人默认接受「每个树节点都当一次起点」的做法，不需要任何字符串哈希或 KMP 级别的优化。同时值域只有 100 意味着重复值很多，匹配到一半失败的情况会频繁出现，写法必须支持失败后从别处重新开始。

边界：树为空时无论链表是什么都返回 false；链表可能只有一个节点，此时只要树里存在这个值就成立。题目保证链表非空。

解法：树上匹配

核心思路

一条路径由「起点 + 每步方向」唯一决定，所以最朴素的想法就是枚举所有起点，对每个起点尝试把链表逐个节点往下贴。问题是从一个起点出发，往下走 $m$ 步有 $2^m$ 条路径，看起来像是指数级。

但注意到匹配是逐位判定、一旦不等立刻失败的：只有当前树节点的值等于当前链表节点的值时，才有必要继续往下试两个孩子。这条剪枝把「枚举所有路径」变成了「沿着值相符的前缀往下走」，实际展开的分支远远小于 $2^m$，最坏也只有 $O(m)$ 量级的有效比较。识别出这一点，暴力枚举就变成了可接受的解法。

于是把问题拆成两个语义完全不同的递归函数，这是本题最核心的设计。

match(head, node) 回答的是：以 node 为路径的当前位置、以 head 为链表的当前位置，能否严格向下匹配完链表剩余部分。它的起点是固定的，不允许中途换起点。

isSubPath(head, root) 回答的是：以 root 为根的整棵子树里，是否存在任意一条向下路径能匹配整条链表。它负责枚举起点。

两者的分工必须泾渭分明。isSubPath 的三支或运算意思是「拿 root 当起点试一次，不行就把整条链表原封不动地丢给左子树、右子树重新找起点」——注意后两支传的是 head 而不是 head.next，因为换起点意味着链表要从头开始。而 match 里传的是 head.next，因为它在同一条路径上继续推进。把这两处的参数搞混，是本题最典型的错误。

match 的三个终止条件顺序也有讲究：先判 head == null 返回 true（链表走完了，匹配成功，此时树节点是不是空都无所谓），再判 node == null 返回 false（链表还有剩余但树已经到底，失败），最后判值不等返回 false。如果把 node == null 放到 head == null 前面，链表恰好在叶子处走完的情况就会被误判为失败。

解题步骤

isSubPath 先处理空树：root == null 时直接返回 false。链表题目保证非空，所以空树里不可能找到任何路径；这个判断同时也是遍历子树时的递归出口。

isSubPath 用短路或串起三种可能：match(head, root) 试当前节点作起点，失败则 isSubPath(head, root.left)、isSubPath(head, root.right) 去左右子树另找起点。用 || 是为了一旦找到就立即停止，避免继续遍历整棵树。

match 第一条终止条件是 head == null 返回 true：链表已经全部匹配完，说明成功。它必须排在最前面，否则「链表最后一个节点正好落在树的叶子上」的情况会被下一条 node == null 抢先判成失败。

match 第二条是 node == null 返回 false：走到这里说明链表还没走完（否则上一条已经返回），而树已经没有节点可用，路径长度不够。

match 第三条是值不等返回 false：当前位置对不上，这条路径作废。注意此时不能就地换起点——换起点是 isSubPath 的职责。

match 递归两个方向：match(head.next, node.left) || match(head.next, node.right)。链表推进一位，树往下走一层；两个孩子都要试，因为题目没规定必须往哪边走。

返回值一路向上短路传递：任何一层拿到 true 就不再计算后面的表达式。

以链表 4 → 2 → 8 和下面这棵树走一遍：根为 1，1 的右孩子是 4，这个 4 的右孩子是 2，2 的左孩子是 1、右孩子是 6，其中 6 的左孩子是 8。

isSubPath(4→2→8, 节点1)：先 match(4→2→8, 节点1)，值 4 ≠ 1，返回 false。左子树为空，isSubPath 返回 false。转到右子树，调用 isSubPath(4→2→8, 节点4)。

isSubPath(4→2→8, 节点4)：先 match(4→2→8, 节点4)。值相等，递归 match(2→8, 节点4的左孩子)——为空，返回 false；再 match(2→8, 节点2)。值 2 相等，继续 match(8, 节点1)——值 8 ≠ 1，返回 false；再 match(8, 节点6)——值 8 ≠ 6，返回 false。于是 match(2→8, 节点2) 返回 false，match(4→2→8, 节点4) 也返回 false。

起点 4 失败后，isSubPath 把完整的链表 4→2→8 交给节点 4 的右子树，即 isSubPath(4→2→8, 节点2)。节点 2 值不等于 4，继续下推到它的孩子 1 和 6，再到 6 的孩子 8，全都匹配不上，最终整体返回 false。

现在把链表换成 2 → 6 → 8 再走一遍关键部分：枚举到节点 2 作起点时，match(2→6→8, 节点2) 值相等，递归 match(6→8, 节点1) 失败，match(6→8, 节点6) 值相等，再递归 match(8, 节点6的左孩子即节点8) 值相等，进而 match(null, ...) 命中第一条终止条件返回 true。true 沿调用链一路短路返回，isSubPath 立即得到 true，后面的兄弟子树完全不会被访问。

这一趟也说明了为什么 match 失败后必须回到 isSubPath 重新枚举起点：起点 4 匹配到一半才失败，若在原地续接就会漏掉后面真正成立的起点。

代码实现

class Solution {
    // match(head, node) 判断从当前树节点向下是否能匹配链表。
    public boolean isSubPath(ListNode head, TreeNode root) {
        if (root == null) {
            return false;
        }

        return match(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
    }

    private boolean match(ListNode head, TreeNode node) {
        if (head == null) {
            return true;
        }
        if (node == null) {
            return false;
        }
        if (head.val != node.val) {
            return false;
        }

        return match(head.next, node.left) || match(head.next, node.right);
    }
}

func isSubPath(head *ListNode, root *TreeNode) bool {
    // match(head, node) 判断从当前树节点向下是否能匹配链表。
    if root == nil {
        return false
    }

    return match(head, root) || isSubPath(head, root.Left) || isSubPath(head, root.Right)
}

func match(head *ListNode, node *TreeNode) bool {
    if head == nil {
        return true
    }
    if node == nil {
        return false
    }
    if head.Val != node.Val {
        return false
    }

    return match(head.Next, node.Left) || match(head.Next, node.Right)
}

复杂度分析

时间复杂度：$O(nm)$，其中 $n$ 是树的节点数、$m$ 是链表长度。外层 isSubPath 访问每个树节点各一次，内层 match 从该节点出发最多向下推进 $m$ 层。虽然 match 每层分叉两次，但只有值相符才会继续展开，最坏情况（树中大量重复值）下单次 match 的开销由链表长度而非 $2^m$ 主导，实际远低于理论上界。

空间复杂度：$O(h + m)$，其中 $h$ 是树高。递归栈由 isSubPath 的深度 $h$ 与 match 的深度 $m$ 叠加而成；树退化成链时 $h = n$，此时为 $O(n)$。没有使用任何额外的数据结构。

关键点总结

枚举起点与固定起点的匹配必须拆成两个函数，各自返回值语义清晰、参数传递方式不同。这个「外层找起点、内层做匹配」的双递归结构在树的子结构类题目里反复出现，是最值得记住的模板。

换起点时传的是原始 head，同一条路径推进时传的是 head.next——这两处参数是本题的分水岭，面试时能主动点出来会很加分。

递归终止条件的顺序本身携带语义：head == null 必须先于 node == null，因为「链表匹配完」优先于「树到底」。写终止条件时先问自己「两个条件同时成立时该返回什么」，答案就决定了顺序。

看似指数级的路径枚举，被「值不等立刻返回」这条剪枝压到了可接受的量级；估复杂度时要把剪枝的效果算进去，而不是机械地按分支数做幂。

短路或 || 不只是写法简洁，它保证了找到答案后立即停止搜索，是这类存在性问题的标准写法。

易错点总结

isSubPath 的后两支误写成 isSubPath(head.next, root.left)：换起点时链表却跟着前进了，链表 4 → 2 → 8 在只有 4 匹配成功的子树里会被当成 2 → 8 继续找，凭空匹配出并不存在的路径。

match 里递归写成 match(head, node.left)：链表原地不动而树一直下沉，1 → 1 这种链表会在任何含有单个 1 的树上返回 true。

match 把 node == null 判在 head == null 之前：链表 1 → 2、树只有根 1 和左孩子 2 时，走到叶子后下一层 node 为空、head 也为空，却先命中 false 分支，正确答案 true 被判成 false。

match 中值不等时就地尝试换起点（比如返回 match(head, node.left)）：这会让链表在同一条路径上任意位置重新开始，链表 1 → 3 在路径 1 → 2 → 3 上会被错误地判为匹配成功。

match 只递归一个孩子：链表 4 → 2 在「4 的右孩子是 2」的树上，若只递归 node.left 会返回 false，而正确答案是 true。

isSubPath 用 && 连接三支：语义变成「三种情况都要成立」，除非树只有一个节点，否则几乎永远返回 false。

在 isSubPath 里漏掉 root == null 判断：递归到叶子的孩子时直接访问 root.left 抛空指针，只要树不是满二叉树就必然触发。

想靠先序遍历串 + KMP 来做：把树拍平成字符串会丢掉「向下」这个约束，1,2,3 的先序串里可能出现 2 和 3 相邻，但它们其实是兄弟而非父子，会误判为存在路径。

匹配成功后仍继续遍历并覆盖结果：用一个全局变量记录答案却在后续分支里写成赋值而非取或，res = match(...) 会被后面失败的分支重新置为 false。

误以为路径必须走到叶子：链表 1 → 2 在「1 的左孩子是 2，2 还有孩子 3」的树上应返回 true，若额外要求 node.left == null && node.right == null 才算成功就会漏解。

相似题目

题目	难度	考察点
剑指 Offer 26. 树的子结构	中等	被匹配的是一棵子树而非一条链，`match` 需同时递归左右两边并取与
572. 另一棵树的子树	简单	要求结构完全相同且延伸到叶子，终止条件比本题更严格
面试题 04.10. 检查子树	中等	与 572 同题，可用序列化后做字符串包含判断
100. 相同的树	简单	只需一次同步比较，不涉及枚举起点，是所有子树匹配题的内层原型
101. 对称二叉树	简单	双指针递归但方向相反，左对右、右对左
112. 路径总和	简单	同样是向下路径，但起点固定为根、终点必须是叶子
437. 路径总和 III	中等	起点终点都自由，可用前缀和哈希把双重递归降到一次遍历
113. 路径总和 II	中等	需要回溯记录完整路径，而非只返回布尔存在性
652. 寻找重复的子树	中等	用序列化 + 哈希表把两两比较降为一次遍历，思路与逐点匹配完全不同
28. 找出字符串中第一个匹配项的下标	简单	一维版的同类问题，失配后可用 KMP 跳过重复前缀而不必回到起点重来