Crack interview 4.4

思想很简单，层序遍历：

#include 
     
      #include 
      
       #include 
       
        using namespace std;struct LinkedListNode{    int value;    LinkedListNode *pNext;};struct BTreeNode{    int value;    BTreeNode *pLeft;    BTreeNode *pRight;    BTreeNode(int v)    {        value = v;        pLeft = NULL;        pRight = NULL;    }};void LinkedBTreeNode(BTreeNode *pRoot, BTreeNode *left, BTreeNode *right){    pRoot->pLeft = left;    pRoot->pRight = right;}//对于每一层存放在layerVector的BTreeNode *们，创建一个LinkedListLinkedListNode *CreateLinkedListByVector(vector
        
          layerVector){    if (layerVector.empty())        return NULL;    //头结点    LinkedListNode *pHead = new LinkedListNode();    vector
         
          ::iterator it = layerVector.begin();    pHead->value = (*it)->value;    pHead->pNext = NULL;    LinkedListNode *pPre = pHead;    LinkedListNode *pCurr = NULL;    it++;    for (; it < layerVector.end(); it++)    {        pCurr = new LinkedListNode();        pCurr->value = (*it)->value;        pCurr->pNext = NULL;        pPre->pNext = pCurr;        pPre = pCurr;    }    return pHead;}//将layerVector中的所有节点的孩子push回traverseQueue中去void PushNextLayer(queue
          
            &traverseQueue, vector
           
             layerVector){ vector
            
             ::iterator it; for (it = layerVector.begin(); it < layerVector.end(); it++) { if ((*it)->pLeft) traverseQueue.push((*it)->pLeft); if ((*it)->pRight) traverseQueue.push((*it)->pRight); }}/*4.4 对于一个BTree，把里面每一层的节点用链表串起来如果有N层，那么就有N个节点*/vector
             
               LinkEachLayer(BTreeNode *pRoot){ vector
              
                returnVector; vector
               
                 layerVector; //用来暂时记录每一层的节点，并创建链表 queue
                
                  traverseQueue; //用来遍历每一层的节点 BTreeNode *pWalker = pRoot; traverseQueue.push(pWalker); while(!traverseQueue.empty()) { //0 首先清空layerVector layerVector.clear(); //1 取出traverseQueue当前所有，就是当前层的所有的节点，push到layerVector中去 while(!traverseQueue.empty()){ layerVector.push_back(traverseQueue.front()); traverseQueue.pop(); } //2 针对layerVector中的节点，create linked list LinkedListNode *pHead = CreateLinkedListByVector(layerVector); //3 把linked list存放到returnVector中去 returnVector.push_back(pHead); //4 最后，将layerVector中的所有节点的孩子再push回traverseQueue中去，进入下一次循环 PushNextLayer(traverseQueue, layerVector); } return returnVector;}int main(){ BTreeNode a(15); BTreeNode b(10); BTreeNode c(27); BTreeNode d(7); BTreeNode e(11); LinkedBTreeNode(&a, &b, &c); LinkedBTreeNode(&b, &d, &e); vector
                 
                   vec = LinkEachLayer(&a); cout<<"hello world!"<
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

 

 

 

 

EOF