题目

题目来源：力扣（LeetCode）

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

示例 1：
image.png
输入：head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true
解释：树中蓝色的节点构成了与链表对应的子路径。

示例 2：
image.png
输入：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
解释：二叉树中不存在一一对应链表的路径。

思路分析

主要思想
遍历每一个节点，判断是否存在以当前节点为起点的路径，其路径上每一节点都与给定的链表节点值一一对应。

二叉树中的每个节点为起点往下的路径是否有与链表相匹配的路径。为了判断是否匹配我们设计一个递归函数 judge(root, head) ，其中 表示当前匹配到的二叉树节点，head 表示当前匹配到的链表节点，整个函数返回布尔值表示是否有一条该节点往下的路径与 head 节点开始的链表匹配，如匹配返回 true，否则返回 false ，一共有四种情况：

  • 链表已经全部匹配完，匹配成功，返回 true
  • 二叉树访问到了空节点，匹配失败，返回 false
  • 当前匹配的二叉树上节点的值与链表节点的值不相等，匹配失败，false
  • 前三种情况都不满足，说明匹配成功了一部分，我们需要继续递归匹配，所以先调用函数judge(root.left, head.next) ，其中root.left 表示该节点的左儿子节点，head.next 表示下一个链表节点，如果返回的结果是 false，说明没有找到相匹配的路径，需要继续在右子树中匹配，继续递归调用函数 judge(root.right, head.next) 去找是否有相匹配的路径，其中root.right 表示该节点的右儿子节点， head.next 表示下一个链表节点。
  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val, next) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.next = (next===undefined ? null : next)
  6.  * }
  7.  */
  8. /**
  9.  * Definition for a binary tree node.
  10.  * function TreeNode(val, left, right) {
  11.  *     this.val = (val===undefined ? 0 : val)
  12.  *     this.left = (left===undefined ? null : left)
  13.  *     this.right = (right===undefined ? null : right)
  14.  * }
  15.  */
  16. /**
  17.  * @param {ListNode} head
  18.  * @param {TreeNode} root
  19.  * @return {boolean}
  20.  */
  21. var isSubPath = function (head, root) {
  22.   // 在一颗树上面找一条空链表肯定能找到
  23.   if (head == null) return true;
  24.   if (root == null) return false;
  25.   // 从root开始捋着比较，是否能找到连续的符合题意的链表
  26.   if (root.val == head.val && judge(root, head)) return true;
  28.   //否则就递归地比较 用树中的每一个节点依次比较链表中的头节点
  29.   return isSubPath(head, root.left) || isSubPath(head, root.right);
  30. };
  31. var judge = function (root, head) {
  32.   // 检查到了链表的末尾，说明找到了一个完整匹配的序列，返回 true
  33.   if (head == null) return true;
  34.   // 链表还未遍历到末尾，树已经遍历到叶子节点，所以不能完全匹配，返回false
  35.   if (root == null) return false;
  36.   // 如果树中的节点已经不匹配了，那么直接返回false
  37.   if (root.val != head.val) return false;
  38.   // 这里证明root节点的值，等于head节点的值
  39.   // 接着向下比较左子树，向下比较右子树
  40.   // 在左右子树中 找到任意一条路径 能够匹配到 链表剩余部分的节点 证明能够匹配成功
  41.   return judge(root.left, head.next) || judge(root.right, head.next);
  42. }