首页 > 代码库 > 笔试算法题（25）：复制拥有多个指针的链表 & 判断二元树B是否为A的子树
笔试算法题（25）：复制拥有多个指针的链表 & 判断二元树B是否为A的子树
出题：定义一个复杂链表：在单向链表的基础上，每个节点附加一个指向链表中其他任意节点的指针sibling，实现CNode* Clone(Cnode *head)函数复制这个复杂链表；
分析：
- 解法1：将head复制到CHead中，第一次遍历创建CHead中对应head的各个节点（next），第二次遍历创建CHead中对应head各个节 点的sibling链接，由于需要在CHead中找到对应head中的sibling节点，所以需要遍历CHead链表，但是可以用空间换时间的方法：使 用Hash Table存储CHead和head对应的节点对，这样head中定位了sibling之后，就可以知道CHead中对应sibling节点，时间复杂度 为O(N)，空间复杂度为O(N)；
- 解法2：注意给出的函数头中参数并没有使用const，而一般情况下的copy函数的参数都是const，所以可以推断可能需要改变原始数据的结构。使用 奇偶链表实现，将新创建的CHead中的各个节点对应安插到head中各个节点之后，这样CHead中与head中对等的节点就在head中节点的后面， 所以可以很容易确定sibling节点，最后仅读取偶数节点就是CHead，时间复杂度为O(N)，空间复杂度为O(1)。海涛老师再次威武！此方法参考 海涛老师的博客：
http://zhedahht.blog.163.com/blog/static/254111742010819104710337/
解题：
1 struct CNode { 2 int value; 3 CNode *next; 4 CNode *sibling; 5 }; 6 CNode* Clone(CNode *head) { 7 if(head==NULL) return NULL; 8 9 CNode *CHead=new CNode(); 10 CHead->value=http://www.mamicode.com/head->value; 11 CNode *cur, *pre=CHead, *temp=head->next, *CTemp; 12 /** 13 * 以next指针为线索创建链表节点 14 * */ 15 while(temp!=NULL) { 16 cur=new CNode(); 17 cur->value=http://www.mamicode.com/temp->value; 18 pre->next=cur; 19 pre=cur; 20 21 temp=temp->next; 22 } 23 /** 24 * 以next指针为线索创建sibling链接 25 * */ 26 temp=head;CTemp=CHead; 27 while(temp!=NULL) { 28 /** 29 * 将下面这句代码换成HashTable存储的head和CHead中 30 * 对等节点的存储对 31 * */ 32 //CTemp->sibling=temp->sibling; 33 temp=temp->next; 34 CTemp=CTemp->next; 35 } 36 return CHead; 37 } 38 /** 39 * 在head中每个节点的后面创建一个新节点， 40 * 并复制之前节点的value，链接之前节点的 41 * next节点 42 * */ 43 void CreateNewNode(CNode *head) { 44 CNode *index=head, *nNode, *next; 45 while(index!=NULL) { 46 nNode=new CNode(); 47 nNode->value=http://www.mamicode.com/index->value; 48 nNode->sibling=NULL; 49 50 next=index->next; 51 index->next=nNode; 52 nNode->next=next; 53 index=next; 54 } 55 } 56 /** 57 * 顺序遍历head中奇数索引的节点，如果其sibling非NULL，则 58 * 其sibling的next节点就是CHead中的对应节点的sibling 59 * */ 60 void CopySibling(CNode *head) { 61 CNode *index=head; 62 while(index!=NULL) { 63 if(index->sibling!=NULL) { 64 index->next->sibling= 65 index->sibling->next; 66 } 67 index=index->next->next; 68 } 69 } 70 /** 71 * 将head拆分成奇数索引节点和偶数索引节点，后者就是新clone 72 * 的复杂链表 73 * */ 74 CNode* Separate(CNode *head) { 75 CNode *index=head, *clone; 76 if(index!=NULL) { 77 clone=index->next; 78 index->next=index->next->next; 79 index=index->next; 80 } else 81 return NULL; 82 CNode *temp; 83 while(index!=NULL) { 84 temp=index->next; 85 clone->next=temp; 86 index->next=temp->next; 87 88 clone=temp; 89 index=temp->next; 90 } 91 92 return clone; 93 } 94 void Deletion(CNode *head) { 95 CNode *cur=head, *next; 96 if(cur!=NULL) { 97 next=cur->next; 98 delete cur; 99 cur=next; 100 } 101 }
出题：输入两棵二元树的根节点A和B，判断B是否是A的一个子树结构；
分析：
- 首先在A中找到与B根节点的值相同的节点AB1（注意处理节点值相同的情况，首先判断当前找到的AB1是否匹配，如果不匹配则继续寻找下一个AB1），然 后同时递归AB1和B，如果B中某节点的值与AB1某节点的值不等，则返回false；
- 如果B中某节点有子节点（左右），而AB1中没有，则返回 false；当B递归完全之后（也就是到达NULL）返回true；
解题：
1 struct Node { 2 int value; 3 Node *left; 4 Node *right; 5 }; 6 /** 7 * son只能是father的一部分，其他情况都返回false 8 * */ 9 bool compare(Node *father, Node *son) { 10 if(son==NULL) return true; 11 if(father==NULL) return false; 12 if(father->value != son->value) 13 return false; 14 else 15 return compare(father->left,son->left) && 16 compare(father->right,son->right); 17 } 18 /** 19 * 注意处理节点值重复的情况，因为只能找到第一个节点，而正确 20 * 的匹配可能发生在之后的拥有相同节点值的节点 21 * */ 22 Node* findNode(Node *root, Node *target) { 23 Node *temp=NULL; bool ismatch=true; 24 if(root->value=http://www.mamicode.com/=target->value) { 25 if(compare(root, target)) { 26 printf("\nb1 is part of a1"); 27 exit(0); 28 } else 29 ismatch=false; 30 } 31 if(!ismatch && root->left!=NULL) 32 temp=findNode(root->left,target); 33 if(temp==NULL && root->right!=NULL) 34 temp=findNode(root->right,target); 35 return temp; 36 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。