二叉树中的链表

难度: Medium

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

示例 1：

输入：head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true
解释：树中蓝色的节点构成了与链表对应的子路径。

示例 2：

输入：head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true

示例 3：

输入：head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：false
解释：二叉树中不存在一一对应链表的路径。

提示：

二叉树和链表中的每个节点的值都满足 1 <= node.val <= 100 。
链表包含的节点数目在 1 到 100 之间。
二叉树包含的节点数目在 1 到 2500 之间。

Submission

运行时间: 42 ms

内存: 16.7 MB

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
        if head==None:
            return True
        if root==None:
            return False
        lib=dict()
        head1=ListNode(0,head)
        lib[head]=head1
        pre,t2=head1,head

        while t2.next!=None:
            while pre!=head1 and pre.val!=t2.val:
                pre=lib[pre]
            lib[t2.next]=pre.next           
            pre=pre.next
            t2=t2.next

        t1, t2=root, head
        stk1=[None]*2501
        stk2=[None]*2501
        size=0
        while t2!=None:
            if t1!=None:
                if t1.val==t2.val:
                    t2=t2.next
                    if t1.left!=None:
                        stk1[size]=t1.left
                        stk2[size]=t2
                        size+=1
                    t1=t1.right
                elif t2!=head:
                    t2=lib[t2]
                else: 
                    if t1.left!=None:
                        stk1[size]=t1.left
                        stk2[size]=t2
                        size+=1
                    t1=t1.right
            elif size>0:
                t1=stk1[size-1]
                t2=stk2[size-1]
                size-=1
            elif size==0:
                return False
        return True

Explain

该题解采用了深度优先搜索（DFS）的方式来判断二叉树中是否存在与链表对应的一条向下的路径。首先，题解中构建了一个失败指针（类似于KMP算法中的失配数组）来优化链表节点的比较过程。使用两个栈来模拟递归的过程，一个栈存储当前待比较的二叉树节点，另一个栈存储当前对应的链表节点。遍历二叉树的每个节点，与当前链表节点比较，如果值相同，则向下移动；如果不匹配，则使用失败指针回退到上一个可能的匹配位置。如果链表的所有节点都成功匹配，则返回真；否则，继续检查二叉树的其他路径。

时间复杂度: O(N + L)

空间复杂度: O(L + H)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
        if head==None:  # 链表为空，则直接返回True
            return True
        if root==None:  # 树为空，则无法匹配，返回False
            return False
        lib=dict()  # 创建失配字典
        head1=ListNode(0,head)  # 创建新的链表头节点，方便处理
        lib[head]=head1  # 失配时的回退点
        pre,t2=head1,head  # 初始化指针

        while t2.next!=None:  # 构建失配字典
            while pre!=head1 and pre.val!=t2.val:
                pre=lib[pre]
            lib[t2.next]=pre.next           
            pre=pre.next
            t2=t2.next

        t1, t2=root, head
        stk1=[None]*2501  # 二叉树节点栈
        stk2=[None]*2501  # 链表节点栈
        size=0  # 栈的当前大小
        while t2!=None:
            if t1!=None:
                if t1.val==t2.val:  # 节点值匹配
                    t2=t2.next  # 向链表下一个节点移动
                    if t1.left!=None:
                        stk1[size]=t1.left  # 将左子节点入栈
                        stk2[size]=t2
                        size+=1
                    t1=t1.right  # 右子节点作为下一个节点
                elif t2!=head:  # 不匹配且不是头节点
                    t2=lib[t2]  # 使用失配字典回退
                else:  # 回到头节点重新开始
                    if t1.left!=None:
                        stk1[size]=t1.left
                        stk2[size]=t2
                        size+=1
                    t1=t1.right
            elif size>0:  # 如果栈非空，回退
                t1=stk1[size-1]
                t2=stk2[size-1]
                size-=1
            elif size==0:  # 栈空，没有匹配路径
                return False
        return True

Explore

在题解中构建链表的失败指针数组（类似于KMP算法中的失配数组）可以显著优化匹配过程。当在二叉树中搜索与链表对应的路径时，如果遇到不匹配的情况，我们可以使用失败指针数组直接跳过一些无需重新检查的节点，这样可以避免从链表的头部重新开始匹配，从而节省了大量的时间。这种方法减少了重复的比较操作，提高了算法的效率。

使用两个栈来模拟递归的过程，相比直接使用递归，有一些优势和不足。优势在于更好的控制递归的过程和管理内存使用，因为递归可能导致栈溢出，尤其是在处理非常大的树或深度非常深的递归调用时。不足之处在于代码复杂度较高，可读性和维护难度都可能增加，同时手动管理栈可能引入错误。

是的，使用失配字典回退到上一个可能的匹配位置可能会导致重复访问某些节点。尤其是在二叉树的结构较为复杂，或者链表与树节点的值频繁不匹配的情况下，这种回退机制可能会多次重试相同的节点，从而影响算法的效率。然而，这种方法仍然比完全重新开始匹配来得更有效率。

如果二叉树的某个分支长度小于链表长度，即使开始的几个节点匹配，最终还是无法完成整个链表的匹配。在这种情况下，一旦二叉树的遍历到达分支末尾但链表尚未完全匹配，算法会停止当前路径的匹配尝试，并回退到上一个分叉点继续尝试其他可能的路径。如果所有可能的路径都无法匹配整个链表，最终结果返回False。