LeetCode 1367. 二叉树中的链表

约 5 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 快手
标签
深度优先搜索 树 二叉树 链表

题目描述

✅ 1367. 二叉树中的链表

image-20260928223955169

image-20260928223955170

题意分析

判断二叉树中能否找到一条连续向下的路径，其节点值依次等于链表的所有节点值。路径可以从任意树节点开始，也可以在任意节点结束，不要求从根到叶子。

连续向下意味着每一步只能去当前节点的左孩子或右孩子：可以在不同层选择不同方向，但不能跳过中间节点，不能向上走，也不能把左右两条分支拼成一条路径。

解法：树上匹配

核心思路

[!blue]

这里有两个不同的问题：一是选择路径从哪个树节点开始，二是选定起点后能否连续匹配完整链表。把它们分成两个递归函数，才能分别维护正确的匹配进度。

外层 isSubPath(head, root) 枚举起点。先尝试从 root 开始匹配；若失败，再去左右子树中寻找其他起点。三次尝试都传入完整的 head，因为更换起点就意味着从链表第一个节点重新匹配。当前树为空时没有起点可选，返回 false。

内层 match(head, node) 固定匹配进度。它表示链表剩余部分能否从树的当前节点开始连续匹配：

  • head 为空，说明所有链表节点已经匹配完，立即成功，不再要求树到达叶子。
  • 链表还没结束，但 node 为空或两者值不同，本次固定起点的尝试失败。
  • 两者值相同，就让链表前进一步，同时分别尝试树的左孩子和右孩子；其中任意一条后续路径成功即可。

必须先判断链表是否结束，再判断树是否为空。最后一项刚好在叶子处匹配时，下一次调用中二者都会为空，这应当算成功。内层不允许在值不同时继续带着原 head 往下找，否则就把“更换起点”混进了“连续匹配”，可能错误地跳过路径中的节点。

外层覆盖所有树节点，保证不会漏掉合法起点；内层每匹配一个链表节点就下降一层，并遍历所有可能的孩子方向，保证固定起点下的所有连续路径都被考虑。两个层次都使用逻辑或，找到一条成功路径就可以停止搜索。

解题步骤

  1. 外层遇到空树返回失败；否则先调用 match(head, root)。
  2. 当前起点失败后，分别对左右子树调用 isSubPath，仍传入完整链表头。
  3. match 先判链表是否耗尽，再判树空或值不同。
  4. 当前值匹配时，调用 match(head.next, node.left) 与 match(head.next, node.right)，任意一侧成功就返回成功。

代码实现

class Solution {

    // 枚举树中的匹配起点，每个起点都从完整链表开始。
    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 {

    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 是链表长度。固定起点的匹配可能在树中分支，不能简单说一次匹配只花 $O(m)$；从全部调用看，一个树节点只可能由它自身或距离小于 m 的祖先作为起点访问，距离 $0$ 到 $m-1$ 各至多对应一个起点，所以至多参与 m 次匹配。
  • 空间复杂度：$O(h)$，其中 h 是树高。外层栈走到某个起点后，内层栈再沿它的后代展开，两部分合起来仍是一条从根向下的树路径；左右分支依次执行，不会同时存下整棵树。

关键点总结

[!green]

  • 换起点使用完整 head，同一路径继续才用 head.next。
  • 存在性使用或，任一分支成功就可结束。

易错点总结

[!yellow]

  • 值不等时仍沿孩子继续同一匹配，会允许跳过节点。
  • 先判树空再判链表结束，会误拒刚好在叶子处完成的匹配。
  • 把树先序拍平后直接查连续子串，可能把兄弟节点误当父子路径。

相似题目

题目 难度 关联与区别
572. 另一棵树的子树 简单 原题匹配整棵子树的结构，本题只要求存在一条向下路径，其余分支不影响匹配。
28. 找出字符串中第一个匹配项的下标 简单 同样让一条模式序列匹配文本，本题文本在树上分支，需要携带当前匹配进度。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/55134376
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！