给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。
如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。
一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。
思路
遍历所有的树节点，如果树节点的val值和链表结点head的val值相等，则进行递归判断。
/**
* 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) {
Queue<TreeNode> queue=new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode tmp=queue.poll();
if (tmp.left != null) queue.add(tmp.left);
if (tmp.right != null) queue.add(tmp.right);
if (tmp.val == head.val) {
// System.out.println(tmp.val);
if (check(tmp, head)) return true;
}
}
return false;
}
public boolean check(TreeNode treeNode, ListNode listNode) {
if (listNode == null) return true;
if (treeNode == null) return false;
if (treeNode.val != listNode.val) return false;
return check(treeNode.left, listNode.next) || check(treeNode.right, listNode.next);
}
}