题目描述

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

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

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

样例

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

输入：head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true

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

限制

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

算法

(递归回溯) $O(nm)$

1. 采用递归回溯，状态表示为当前链表的头结点，当前树上的结点，以及是否已经开始了匹配。
2. 递归出口：如果当前链表的头结点为空，则返回匹配成功；如果当前链表的头结点不为空，但树上结点为空，则返回匹配失败。
3. 如果已经未开始匹配，则如果当前对应的值相等，则可以选择开始匹配，或者不开始匹配，分四种情况递归；如果对应值不相等，则只能选择不开始匹配，分两种情况递归。
4. 如果已经开始匹配，但当前对应值不相等，则返回匹配失败；否则分两种情况继续递归。

时间复杂度

• 最坏情况下，每个位置都有可能作为开始位置进行匹配，故时间复杂度为 $O(nm)$。

空间复杂度

• 需要额外 $O(\min(n, m))$ 作为系统栈空间。

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool solve(ListNode *head, TreeNode *root, bool start) {
        if (head == NULL) return true;
        if (root == NULL) return false;

        if (!start) {
            if (head->val == root->val)
                return solve(head->next, root->left, true)
                    || solve(head->next, root->right, true)
                    || solve(head, root->left, false)
                    || solve(head, root->right, false);

            return solve(head, root->left, false)
                    || solve(head, root->right, false);

        } else {
            if (head->val != root->val) return false;

            return solve(head->next, root->left, true)
                || solve(head->next, root->right, true);
        }
    }

    bool isSubPath(ListNode* head, TreeNode* root) {
        return solve(head, root, false);
    }
};