16 合并两个排序的链表
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
示例
输入
输出
思路：
比较两个链表当前指针值的大小，小的那个加到新链表中，指针后移。循环遍历只要有一个链表为空，将剩下的链表添到新链表后面。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
ListNode node(0);
ListNode *res=&node;
while(pHead1!=nullptr&&pHead2!=nullptr){
if(pHead1->val<pHead2->val){
res->next=pHead1;
pHead1=pHead1->next;
}
else{
res->next=pHead2;
pHead2=pHead2->next;
}
res=res->next;
}
res->next=pHead1==nullptr?pHead2:pHead1;
return node.next;
}
};
|
17 树的子结构
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
示例
输入
1
| {8,8,#,9,#,2,#,5},{8,9,#,2}
|
输出
思路：
俩个树都不为空的时候开始比较，遍历pRoot1树的每一个节点找到值和pRoot2相同的节点
根节点值相同后开始比较，若其左右子树都相同则返回true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
bool res=false;
if(pRoot1==nullptr||pRoot2==nullptr)return res;
if(pRoot1->val==pRoot2->val){
res=isSubTree(pRoot1, pRoot2);
}
if(!res){
return HasSubtree(pRoot1->left,pRoot2)
||HasSubtree(pRoot1->right,pRoot2);
}
return res;
}
bool isSubTree(TreeNode* pRoot1, TreeNode* pRoot2){
if(pRoot2==nullptr)return true;
if(pRoot1==nullptr)return false;
if(pRoot1->val==pRoot2->val){
return isSubTree(pRoot1->left,pRoot2->left)
&&isSubTree(pRoot1->right, pRoot2->right);
}
else return false;
}
};
|
18 二叉树的镜像
题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
1
2
3
4
5
6
7
8
9
10
11
12
| 比如： 源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
|
思路：
翻转节点的左右子树，递归调用函数确保每一个节点的左右子树都做出互换。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
TreeNode* Mirror(TreeNode* pRoot) {
if(pRoot==nullptr)return nullptr;
TreeNode *temp=pRoot->left;
pRoot->left=pRoot->right;
pRoot->right=temp;
Mirror(pRoot->left);
Mirror(pRoot->right);
return pRoot;
}
};
|
