题目：对于一颗完全二叉树，要求给所有节点加上一个pNext指针，指向同一层的相邻节点；如果当前节点已经是该层的最后一个节点，则将pNext指针指向NULL；给出程序实现，并分析时间复杂度和空间复杂度。

答：时间复杂度为O(n),空间复杂度为O(1)。

#include "stdafx.h"#include 
     
      #include 
      
       #include 
       
        using namespace std;struct TreeNode {    int m_nValue;    TreeNode *m_pLeft;    TreeNode *m_pRight;    TreeNode *pNext;};//假定所创建的二叉树如下图所示/*                                             1                                          /     \                                         2       3                                        / \      / \                                       4   5    6   7                                      / \  / \  / \                                     8   9 10 11 12 13*/void CreateBitree(TreeNode *&pNode, fstream &fin){    int dat;    fin>>dat;    if(dat == 0)    {        pNode = NULL;    }    else     {        pNode = new TreeNode();        pNode->m_nValue = dat;        pNode->m_pLeft = NULL;        pNode->m_pRight = NULL;        pNode->pNext = NULL;        CreateBitree(pNode->m_pLeft, fin);              CreateBitree(pNode->m_pRight, fin);     }}//完全二叉树指向同一层的相邻结点void Solution(TreeNode *pHead){    if (NULL == pHead)    {        return;    }    vector
        
          vec;    vec.push_back(pHead);    TreeNode *pre = NULL;    TreeNode *pNode = NULL;    int cur = 0;    int last = 0;    while(cur < vec.size())    {        last = vec.size();        while (cur < last)        {            if (NULL == pre)            {                pre = vec[cur];            }            else            {                pre->pNext = vec[cur];            }            if (NULL != vec[cur]->m_pLeft)            {                vec.push_back(vec[cur]->m_pLeft);            }            if (NULL != vec[cur]->m_pRight)            {                vec.push_back(vec[cur]->m_pRight);            }            pre = vec[cur];            cur++;        }        pre->pNext = NULL;        pre = NULL;    }}int _tmain(int argc, _TCHAR* argv[]){    fstream fin("tree.txt");    TreeNode *pHead = NULL;    TreeNode *pNode = NULL;    CreateBitree(pHead, fin);    Solution(pHead);    while (NULL != pHead)    {        cout<
         
          m_nValue<<"  ";        pNode = pHead->pNext;        while (NULL != pNode)        {            cout<
          
           m_nValue<<" "; pNode = pNode->pNext; } cout<
           
            m_pLeft; } cout<
           
          
         
        
       
      
     

运行界面如下：

建造二叉树用到的tree.txt文件如下:

1 2 4 8 0 0 9 0 0 5 10 0 0 11 0 0 3 6 12 0 0 13 0 0 7 0 0