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

【LeetCode】剑指 Offer（9）

news 2025/8/6 0:59:59

题目：剑指 Offer 25. 合并两个排序的链表 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过啦！！！

题目：剑指 Offer 26. 树的子结构 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过啦！！！

写在最后：

题目：剑指 Offer 25. 合并两个排序的链表 - 力扣（Leetcode）

题目的接口：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {}
};

解题思路：

我的思路是用一个简单的归并思想，

两个链表对比，

值小的就提取出来，

最后集合成一个新链表。

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {//建一个哨兵位的头结点ListNode* head = new ListNode(0);//新链表的头指针ListNode* cur = head;//归并while(l1 && l2){if(l1->val < l2->val){cur->next = l1;l1 = l1->next;}else{cur->next = l2;l2 = l2->next;}cur = cur->next;}//如果有一个链表遍历完了，那就//直接用新链表的尾将剩下的那个链表接上cur->next = (l1 == nullptr ? l2 : l1);//返回新链表的头return head->next;}
};

过啦！！！

题目：剑指 Offer 26. 树的子结构 - 力扣（Leetcode）

题目的接口：

/*** 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 isSubStructure(TreeNode* A, TreeNode* B) {}
};

解题思路：

有关二叉树的遍历，一般就想到递归，

用递归遍历整个A树，

然后用每个根节点与B树比较，

如果递归到空，节点的值都相等，就返回true。

代码：

/*** 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 is_SubStructure(TreeNode* A, TreeNode* B){//如果递归到空节点，证明B是A的子结构if(B == nullptr){return true;}//如果A走到空节点，或者不相等，返回falseif(A == nullptr || A->val != B->val){return false;}//比较左孩子和右孩子return is_SubStructure(A->left, B->left) && is_SubStructure(A->right, B->right);}bool isSubStructure(TreeNode* A, TreeNode* B) {//判断树是否为空if(A == nullptr || B == nullptr){return false;}//递归比较节点                  //遍历二叉树return is_SubStructure(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);}
};