正文
c++刷题（30/100）
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
题目一：合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路：利用两个指针cur1，cur2来指分别向两个链表中当前较小的和当前较大的节点，若cur1->val>cur2->val，那么就将两者交换
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
ListNode* pre = NULL;
ListNode* next = NULL;
if(pHead1==NULL||pHead2==NULL){
return pHead1!=NULL ? pHead1 : pHead2 ;
}
ListNode* head = pHead1->val<pHead2->val ? pHead1 : pHead2 ;
ListNode* cur1 = head==pHead1? pHead1 : pHead2 ;
ListNode* cur2 = head==pHead1? pHead2 : pHead1 ;
while(cur1!=NULL&&cur2!=NULL){
if(cur1->val<=cur2->val){
pre = cur1 ;
cur1 = cur1->next ;
}else{
next = cur1 ;
pre->next = cur2 ;
pre = cur2 ;
cur1 = cur2 ;
cur2 = next ;
}
}
pre->next = cur1!=NULL? cur1 : cur2 ;
return head ;
}
};
题目二：树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路：判断B是A的子结构，所以每次判断都是判断A的某个节点subA和B的根节点开始是否能找到一个相等的树，这个相等是有条件的，当B的节点遍历到空的时候，如果subA不为空，那么也算是相等。
所以写一个判断是否“相等”的函数，然后让A的每个节点都和B的根节点带入这个函数比较就行了
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
bool isEqual(TreeNode* pRoot1, TreeNode* pRoot2){
if(pRoot2==NULL) return true ;
if(pRoot1==NULL) return false ;
if(pRoot1->val!=pRoot2->val) return false ;
if(isEqual(pRoot1->left,pRoot2->left)&&isEqual(pRoot1->right,pRoot2->right)) return true ;
return false ;
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot2==NULL||pRoot1==NULL) return false ;
if(isEqual(pRoot1,pRoot2)) return true ;
return HasSubtree(pRoot1->left,pRoot2)||HasSubtree(pRoot1->right,pRoot2) ;
}
};
题目三：二叉树镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
思路：就是简单的左右孩子互换，递归实现就好了
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
void Mirror(TreeNode *pRoot) {
if(pRoot==NULL) return ;
Mirror(pRoot->left) ;
Mirror(pRoot->right) ;
TreeNode *temp = pRoot->left ;
pRoot->left = pRoot->right ;
pRoot->right = temp ;
}
};
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
思路：就是简单的左右孩子互换，递归实现就好了
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
void Mirror(TreeNode *pRoot) {
if(pRoot==NULL) return ;
Mirror(pRoot->left) ;
Mirror(pRoot->right) ;
TreeNode *temp = pRoot->left ;
pRoot->left = pRoot->right ;
pRoot->right = temp ;
}
};
