LeetCode1367.LinkedListinBinaryTree二叉树中的列表【Medium】【Python】【DFS】问题LeetCode给定一个二叉树根和一个链表，头为第一个节点。如果从头开始的链表中的所有元素都对应于二叉树中连接的某个向下路径，则返回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]输出：trueExplanation：蓝色的节点在二叉树中形成一个子路径。示例2：输入：head=[1,4,2,6]，root=[1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]Output:trueExample3:Input: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解释：二叉树中不存在包含来自的链表的所有元素的路径head.Constraints:1<=node.val<=100对于链表和二叉树中的每个节点。给定的链表将包含1到100个节点。给定的二叉树将包含1到2500个节点。问题force我会给你一个以root为根的二叉树和一个以head为第一个节点的链表。如果在二叉树中，有一条路径一直往下走，每个点的值和以head为首的链表正好一一对应。每个节点的值，那么请返回True，否则返回False。Apaththatgoesallwaydown的意思是：从树中的某个节点开始，一直往下走的路径。示例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个节点。DFS有两种思路，第一种：找起点。先判断当前节点，如果不是则判断左子树和右子树。第二阶段：从找到的起点判断剩余的点。Python3代码#单链表的定义。#classListNode:#def__init__(self,x):#self.val=x#self.next=None#二叉树节点的定义。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：defisSubPath(self,head:ListNode,root:TreeNode)->bool:ifhead==None:returnTrueifroot==None:returnFalse#判断root，再判断root.left和root.rightreturnself.isSub(head,root)orself.isSubPath(head,root.left)orself.isSubPath(head,root.right)defisSub(self,head,node):#list结束ifhead==None:returnTrue#list没有结束，tree结束ifnode==None:returnFalse#notequalifnothead.val==node.val:returnFalse#相等，则左右returnself.isSub(head.next,node.left)orself.isSub(head.next,node.right)代码地址GitHub链接参考JerrySenior'sSolution
