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

Leecode刷题C语言之二叉树中的链表

news 2025/1/3 0:17:32

执行结果:通过

执行用时和内存消耗如下：

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);
}

解题思路：

这段代码是用来判断一个链表（head）是否是另一个二叉树（root）中某条从根节点开始的路径。下面是代码的思路详解：

`dfs` 函数

dfs 函数是深度优先搜索（Depth-First Search）的实现，用于检查从给定的二叉树节点 rt 开始，是否存在一条路径能够与链表 head 完全匹配。

参数：
- struct TreeNode* rt：当前遍历到的二叉树节点。
- struct ListNode* head：当前需要匹配的链表节点。
返回值：
- bool：如果找到匹配的路径，返回 true；否则返回 false。
思路：
1. 链表已经全部匹配完：如果 head 为 NULL，表示链表中的所有节点都已经成功匹配，返回 true，表示找到了一条匹配的路径。
2. 二叉树访问到了空节点：如果 rt 为 NULL，表示在二叉树中无法继续向下匹配了，但链表还未匹配完，因此返回 false。
3. 当前匹配的二叉树上节点的值与链表节点的值不相等：如果当前二叉树节点的值 rt->val 不等于链表节点的值 head->val，则这条路径不可能匹配，返回 false。
4. 递归匹配：
  - 尝试从左子树开始匹配：dfs(rt->left, head->next)。
  - 如果左子树不匹配，再尝试从右子树开始匹配：dfs(rt->right, head->next)。
  - 使用逻辑或 || 操作符，只要有一边匹配成功，整个 dfs 函数就返回 true。

`isSubPath` 函数

isSubPath 函数用于判断链表是否是二叉树中某条路径的子路径。

参数：
- struct ListNode* head：链表头节点。
- struct TreeNode* root：二叉树根节点。
返回值：
- bool：如果链表是二叉树中某条路径的子路径，返回 true；否则返回 false。
思路：
1. 二叉树为空：如果 root 为 NULL，表示整个二叉树为空，链表不可能是其路径，返回 false。
2. 尝试从当前节点开始匹配：调用 dfs(root, head) 尝试从当前二叉树根节点开始匹配链表。
3. 递归尝试左右子树：
  - 如果当前节点开始的匹配失败，则递归地在左子树中继续尝试：isSubPath(head, root->left)。
  - 如果左子树也失败，则在右子树中继续尝试：isSubPath(head, root->right)。
4. 逻辑或操作：使用逻辑或 || 操作符，只要有一边返回 true，表示找到了匹配的路径，整个 isSubPath 函数就返回 true。