给你一棵以 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
解释：树中蓝色的节点构成了与链表对应的子路径。
基本思路： 其实思路很简单，我们要在二叉树中找到一条自上到下的路径，该路径上的结点的值跟链表的值都相同，我们可以使用递归来解决这个问题,当当前结点的值跟链表结点的值相同时，我们就对链表下一个结点的值跟树的左右孩子结点比较，只要左右孩子有一个比较成功，那就可以说明匹配成功了，如果匹配不成功，那就对以左右孩子为根结点的树重新进行匹配，直到所有结点匹配完，进行匹配的函数为isSub
return isSub(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
//只要一个成立，就能说明匹配成功，所以用||操作
递归出口：使用递归要明确递归出口，那递归出口应该是什么？递归出口就是结点为空或者链表为空时，当结点为空，说明树的结点都遍历完了，那还没匹配到的话，就可以返回false了，当链表为空时，说明链表匹配完了，那就可以返回true
if(head == null)
return true;
if(root == null)
return false;
完整代码
class Solution {
public boolean isSubPath(ListNode head, TreeNode root) {
if (head == null) {
return true;
}
if (root == null) {
return false;
}
//先判断当前的节点，如果不对，再看左子树和右子树
return isSub(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
}
private boolean isSub(ListNode head, TreeNode node)
//匹配函数就是让树的结点跟子节点一起往下遍历，只要一个不匹配，就返回false
{
if(head == null)
return true;
if node == null)
return false;
if (head.val != node.val)
return false;
//这里直接就剪枝了，但是你不用担心后面的子树是否有符合匹配条件的被剪掉了，
在isSubPath函数里面对所有子树都调用了isSub匹配函数
return isSub(head.next, node.left) || isSub(head.next, node.right);
}
}
注意：该代码是互相递归的，可能一开始看起来有点懵
该解法来源于：
作者：jerry_nju
链接：https://leetcode-cn.com/problems/linked-list-in-binary-tree/solution/zhe-ti-jiu-shi-subtreeyi-mao-yi-yang-by-jerry_nju/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
我自己的解法是：
class Solution {
public boolean isSubPath(ListNode head, TreeNode root) {
return isSubPath(head,root,head);
}
public boolean isSubPath(ListNode head, TreeNode root, ListNode NextNode)
{
if(NextNode==null)
return true;
if(root==null)
return false;
//递归退出条件是一样的
if(root.val!=NextNode.val) //当当前结点的值跟链表的值不相同时，就要对链表重头开始遍历
{
boolean l = isSubPath(head,root.left,head);
boolean r = isSubPath(head,root.right,head);
return l||r;
}
else
{
boolean l = isSubPath(head,root.left,NextNode.next);
boolean r = isSubPath(head,root.right,NextNode.next);
return l||r;
}
}
}
这个解法我觉得是没有问题的，但是就在一个特殊的案例就通不过，我也没啥办法
我之前刷了十几道动态规划的题，感觉动态规划是最难的，二叉树还行，思路很快就能出来了，只要实现就行，但是动态规划就是看题看很久都没有半点思路，所以我先不练动态规划了，先刷一下树的题