笔试算法题（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=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=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=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==target->value) {
25                 if(compare(root, target)) {
26                         printf("
b1 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 }