4.4 给定一棵二叉树，设计一个算法，创建含有某一深度上所有结点的链表（比如，若一棵树的深度为D，则会创建D个链表）。
类似于leetcode：Populating Next Right Pointers in Each Node II
解答
这道题目本质上是个BFS，也就是说，如果已经构建了第i层结点的链表， 那么将此链表中每个结点的左右孩子结点取出，即可构建第i+1层结点的链表。 设结点类型为TreeNode，那么指向每一层链表头结点的类型为list<TreeNode*>， 将每一层头结点指针放到vector中。如果当前层的链表不为空， 那么将该链表的结点依次取出，然后将这些结点的不为空的孩子放入新的链表中。
C++实现代码：
#include<vector>
#include<iostream>
#include<list>
using namespace std; struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}; TreeNode* helper(vector<int>::iterator begin,vector<int>::iterator end)
{
TreeNode *root=NULL;
if(begin+==end)
return new TreeNode(*begin);
if(begin>=end)
return NULL;
int mid=(end-begin-)/;
root=new TreeNode(*(begin+mid));
root->left=helper(begin,begin+mid);
root->right=helper(begin+mid+,end);
return root;
} TreeNode* createAVL(vector<int> &vec)
{
if(vec.empty())
return NULL;
return helper(vec.begin(),vec.end());
} vector<list<TreeNode*> > find_level_linklists(TreeNode *root)
{
list<TreeNode*> ll;
vector<list<TreeNode*> > ret;
ll.push_back(root);
ret.push_back(ll);
while(!ll.empty())
{
list<TreeNode*> tmp=ll;
ll.clear();
auto iter=tmp.begin();
while(iter!=tmp.end())
{
TreeNode *node=*iter;
if(node->left)
ll.push_back(node->left);
if(node->right)
ll.push_back(node->right);
iter++;
}
if(!ll.empty())
ret.push_back(ll);
}
return ret;
} void print(vector<list<TreeNode*> > res)
{
vector<list<TreeNode*> >::iterator vit;
for(vit=res.begin(); vit!=res.end(); ++vit)
{
list<TreeNode*> li = *vit;
list<TreeNode*>::iterator lit;
for(lit=li.begin(); lit!=li.end(); ++lit)
{
TreeNode *n = *lit;
cout<<n->val<<" ";
}
cout<<endl;
}
} int main()
{
vector<int> vec= {,,,,,,,,,};
TreeNode *root=createAVL(vec);
vector<list<TreeNode*> > res=find_level_linklists(root);
print(res);
}
运行结果：