lintcode 242. 将二叉树按照层级转化为链表

给一棵二叉树，设计一个算法为每一层的节点建立一个链表。也就是说，如果一棵二叉树有 D 层，那么你需要创建 D 条链表。

样例
样例 1:
输入: {1,2,3,4}
输出: [1->null,2->3->null,4->null]
解释:
1
/ 
2
3
/
4
样例 2:
输入: {1,#,2,3}
输出: [1->null,2->null,3->null]
解释:
1

2
/
3

思路：利用双队列，将根结点加入a队列，b队列则存放a队列的后的节点，生成第一层的链表，再将b队列的孩子放入a队列，b队列依次出队得到第二层链表，以此类推，得到最后一层。

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*
int val;
*
TreeNode *left, *right;
*
TreeNode(int val) {
*
this->val = val;
*
this->left = this->right = NULL;
*
}
* }
* Definition for singly-linked list.
* struct ListNode {
*
int val;
*
ListNode *next;
*
ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
/**
* @param root the root of binary tree
* @return a lists of linked list
*/
vector<ListNode*> binaryTreeToLists(TreeNode* root) {
// Write your code here
vector<ListNode*> res;
if(!root) return res;
queue<TreeNode*>a;
queue<TreeNode*>b;
a.push(root);
while(!a.empty()||!b.empty())
{
if(!a.empty())
{
ListNode*head=new ListNode(0);
while(!a.empty()) {
/* code */
ListNode*p=new ListNode(a.front()->val);
insert(head,p);
if(a.front()->left)b.push(a.front()->left);
if(a.front()->right)b.push(a.front()->right);
a.pop();
}
res.push_back(head->next);
//
a.clear();
}
if(!b.empty())
{
ListNode*head=new ListNode(0);
while(!b.empty()){
/* code */
ListNode*p=new ListNode(b.front()->val);
insert(head,p);
if(b.front()->left)a.push(b.front()->left);
if(b.front()->right)a.push(b.front()->right);
b.pop();
}
res.push_back(head->next);
}
}
return res;
}
void insert(ListNode*&head,ListNode*node)
{
ListNode*p=head;
while(p->next)p=p->next;
p->next=node;
return;
}
};

最后

以上就是机智心锁为你收集整理的lintcode 242. 将二叉树按照层级转化为链表的全部内容，希望文章能够帮你解决lintcode 242. 将二叉树按照层级转化为链表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。