1367. Linked List in Binary Tree

题目信息

题号:

1367

难度:

Medium

主题:

链表、二叉树、路径匹配

原题:

LeetCode 1367

重点:

链表必须匹配树中从某个节点开始、每步向左或向右的连续向下路径

题目重述

给定一个非空单链表 head 和一棵非空二叉树 root。请判断树中是否存在某个起始节点,使从该节点沿孩子方向向下的一条路径,其节点值依次与链表全部节点值相同。

路径可以从树中任意节点开始,但不能向上移动或跳过树节点,且必须完整匹配整条链表。

链表节点数不超过 100,树节点数不超过 2500,节点值位于 [1,100]。

自建示例

匹配路径可以从非根节点开始:

输入:head = [4,2], root = [1,4,3,null,2]
输出:true
解释:从值为 4 的左孩子开始,向右下到值为 2 的节点,完整匹配链表。

后继值不一致时失败:

输入:head = [1,2], root = [1,null,3]
输出:false
解释:树中值为 1 的节点只有值为 3 的孩子。