当前位置：首页 > article >正文

Leetcode打卡：二叉树中的链表

article 2025/1/5 10:30:21

执行结果：通过

题目 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);


}

解题思路：

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