Leetcode打卡：二叉树中的链表

执行结果：通过

题目 1367 二叉树中的链表

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

提示：

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

代码以及解题思路

代码

bool dfs(struct TreeNode* rt, struct ListNode* head) {if (head == NULL) {return true;}if (rt == NULL) {return false;}if (rt->val != head->val) {return false;}return dfs(rt->left, head->next) || dfs(rt->right, head->next);
}bool isSubPath(struct ListNode* head, struct TreeNode* root) {if (root == NULL) {return false;}return dfs(root, head) || isSubPath(head, root->left) || isSubPath(head, root->right);}

解题思路：

1. 深度优先搜索（DFS）函数 dfs：
   • 参数：接收一个二叉树的节点 rt 和一个链表的节点 head 作为参数。
   • 终止条件：
     • 如果链表已经遍历完（head == NULL），说明当前路径匹配成功，返回 true。
     • 如果二叉树节点为空（rt == NULL），说明当前路径无法继续匹配，返回 false。
     • 如果当前二叉树节点的值与链表节点的值不相等（rt->val != head->val），说明当前路径不匹配，返回 false。
   • 递归逻辑：
     • 如果当前节点匹配成功，则尝试向左子树或右子树继续匹配链表的下一个节点，即 dfs(rt->left, head->next) 或 dfs(rt->right, head->next)。
     • 使用逻辑或 || 是因为只要有一边匹配成功，整个路径就匹配成功。
2. 主函数 isSubPath：
   • 参数：接收链表的头节点 head 和二叉树的根节点 root 作为参数。
   • 终止条件：
     • 如果二叉树根节点为空（root == NULL），说明无法继续搜索，返回 false。
   • 递归逻辑：
     • 首先尝试从当前根节点开始匹配整个链表，即 dfs(root, head)。
     • 如果从当前根节点开始匹配不成功，则递归地对左子树和右子树调用 isSubPath 函数，即 isSubPath(head, root->left) 或 isSubPath(head, root->right)。
     • 使用逻辑或 || 是因为只要有一边（根节点开始、左子树或右子树）能找到匹配的路径，整个函数就返回 true。

总结

• dfs 函数用于判断从二叉树的某个节点开始是否能匹配整个链表。
• isSubPath 函数用于递归地遍历二叉树的每个节点，作为可能的路径起点，调用 dfs 函数进行匹配。
• 这两个函数共同实现了在二叉树中查找与给定链表完全相同的路径的功能。