目录
题目：剑指 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走到空节点，或者不相等，返回false
-
if(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);
-
}
-
};
过啦！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
转载：https://blog.csdn.net/Locky136/article/details/129178678
查看评论