将二叉树中每一层的节点串成链表

Crack interview 4.4

思想很简单，层序遍历：

#include <iostream>
#include <vector>
#include <queue>
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 *们，创建一个LinkedList
LinkedListNode *CreateLinkedListByVector(vector<BTreeNode *> layerVector)
{
    if (layerVector.empty())
        return NULL;

    //头结点
    LinkedListNode *pHead = new LinkedListNode();
    vector<BTreeNode *>::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<BTreeNode *> &traverseQueue, vector<BTreeNode *> layerVector)
{
    vector<BTreeNode *>::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<LinkedListNode*> LinkEachLayer(BTreeNode *pRoot)
{
    vector<LinkedListNode *> returnVector;
    vector<BTreeNode *> layerVector;            //用来暂时记录每一层的节点，并创建链表
    queue<BTreeNode *> 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<LinkedListNode *> vec = LinkEachLayer(&a);
    cout<<"hello world!"<<endl;
    return 0;
}

EOF