首页 > 代码库 > careercup-树与图 4.4
careercup-树与图 4.4
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+1==end) return new TreeNode(*begin); if(begin>=end) return NULL; int mid=(end-begin-1)/2; root=new TreeNode(*(begin+mid)); root->left=helper(begin,begin+mid); root->right=helper(begin+mid+1,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= {1,2,3,4,5,6,7,8,9,10}; TreeNode *root=createAVL(vec); vector<list<TreeNode*> > res=find_level_linklists(root); print(res);}
运行结果：
careercup-树与图 4.4
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。