无锡做网站企业,网站建设项目签约仪式举行,宝尊代运营一年要多少钱,网络营销的策略有哪些一、树的子结构
1.链接
树的子结构_牛客题霸_牛客网 (nowcoder.com)
2.描述
给两颗二叉树A B#xff0c;判断B是不是A的子结构
3.思路
将问题拆解开来#xff0c;首先是找到a树中子结构的位置#xff0c;然后是判断是否相同#xff0c;也就是说#xff0c;我们需要去…一、树的子结构
1.链接
树的子结构_牛客题霸_牛客网 (nowcoder.com)
2.描述
给两颗二叉树A B判断B是不是A的子结构
3.思路
将问题拆解开来首先是找到a树中子结构的位置然后是判断是否相同也就是说我们需要去遍历一边a树逐一把每个节点作为根去和b的根进行判断是否相同如果相同则说明确实是子结构此外题目还要求空树不属于任何树的子结构
4.参考代码
ps:一开始理解错了子结构的意思理解成子树了所以判断是否子结构的函数名字写的是is_same
class Solution
{
public:bool is_same(TreeNode* A, TreeNode* B){if(B nullptr){return true;}if(A nullptr){return false;}if(A-val ! B-val){return false;}return is_same(A-left, B-left) is_same(A-right, B-right);}bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {if(pRoot1 nullptr || pRoot2 nullptr){return false;}bool ret is_same(pRoot1, pRoot2);if(ret){return true;}else{return HasSubtree(pRoot1-left, pRoot2) || HasSubtree(pRoot1-right,pRoot2);}}
};二、二叉树的镜像
1.链接
二叉树的镜像_牛客题霸_牛客网 (nowcoder.com)
2.描述
操作给定的二叉树将其变换为源二叉树的镜像。 3.思路
通过观察发现镜像后就是原二叉树每个节点的左右子树交换因此很容易想到用递归的方法遍历每个节点然后去将每个节点的左右子树交换遇到空则返回
4.参考代码
class Solution {
public:TreeNode* Mirror(TreeNode* pRoot) {if(pRoot nullptr){return nullptr;}TreeNode* tmp pRoot-left;pRoot-left pRoot-right;pRoot-right tmp;Mirror(pRoot-left);Mirror(pRoot-right);return pRoot;}
}; 三、删除链表重复节点
1.链接
删除链表中重复的结点_牛客题霸_牛客网 (nowcoder.com)
2.描述
给一个单链表要求删掉所有重复的区间一个不留然后返回
3.思路 4.参考代码
class Solution {
public:ListNode* deleteDuplication(ListNode* pHead) {if(pHead nullptr){return nullptr;}ListNode* newhead new ListNode(0);newhead-next pHead;ListNode* fast pHead;ListNode* slow newhead;while(fast){while(fast-next fast-val ! fast-next-val){fast fast-next;slow slow-next;}while(fast-next fast-val fast-next-val){fast fast-next;}if(slow-next ! fast){slow-next fast-next;}fast fast-next;}ListNode* ret newhead-next;delete newhead;return ret;}
}; 总结
这次的总结前两题主要考递归和对二叉树的控制第三题考验的是对单链表的控制和对边界条件的考虑。
