科技让生活更美好作文500字_成都有哪些好玩的地方和景点_电商网站建设定制_百度开放平台

问题背景

给你一棵以 $root$ 为根的二叉树和一个 $head$ 为第一个节点的链表。
如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 $head$ 为首的链表中每个节点的值，那么请你返回 $True$，否则返回 $False$。
一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

数据约束

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

解题过程

链表可以看作退化的二叉树，参考 检查子树，找链表和找子树是很类似的。
区别在于，链表不要求和树结构完全一致，所以递归过程中部分逻辑细节要修改一下。

具体实现

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSubPath(ListNode head, TreeNode root) {// 底下要用对 root 的对象进行引用，必须特判它为空的情形// 待查找的树已经为空，无法进一步匹配，结果应该是 falseif(root == null) {return false;}// 当前节点上可能找到链表的情况下，递归判断左右子树return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);}private boolean dfs(ListNode head, TreeNode root) {// 链表已经遍历完毕，说明找到了这样的结构，返回 trueif(head == null) {return true;}// 链表尚未遍历完毕，树已经空了或者当前节点的值不相等，不用继续往下递归了if(root == null || head.val != root.val) {return false;}// 递归到左右子树上，进一步判断是否符合条件return dfs(head.next, root.left) || dfs(head.next, root.right);}
}