leetcode第1637题（中等）

原链接：https://leetcode-cn.com/problems/linked-list-in-binary-tree/

问题描述

给你一棵以 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
解释：二叉树中不存在一一对应链表的路径。

解题思路

枚举，递归，深度优先搜索dfs

枚举二叉树得所有节点，从某节点开始递归以该节点为头节点得子树（使用深度优先搜索算法）。递归过程中如果满足链表中所有节点都能和该子树的节点对应返回true，否则返回false。

不满足条件的情况可能有：

• 1.二叉树到达叶子节点，但是链表没有到最后一个节点
• 2.二叉树和链表对应的节点的值不相等

代码（java）

/**
 * 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) {
        if(root==null){
            return false;
        }
        return dfs(head,root) || isSubPath(head,root.left) || isSubPath(head,root.right);
    }
    public boolean dfs(ListNode head, TreeNode root){
        if(head==null){
            return true;
        }
        if(root==null){
            return false;
        }
        if(root.val!=head.val){
            return false;
        }
        return dfs(head.next,root.left)||dfs(head.next,root.right);
    }
}