Binary Tree to Linked List
出处
Covert a binary tree to linked lists. Each linked list is correspondent to all the nodes at the same level.
Solution
本题相当于层次遍历,当遍历完一层时将构成的链表加入链表集合。本题的核心在于如何判断某层已经遍历完成。回顾层次遍历,我们将节点逐次放入优先队列,然后一次弹出,并将左右子节点放入队列。我们可以引入一个特别的哑节点,用来作为层与层之间的分隔符。每当发现当前节点是哑节点,则说明当前层已经遍历完毕,也意味着下一层的所有节点都已经进入队列。此时,立刻再推送一个哑节点入队,作为下一层的分隔符。
Complextiy
算法需要层次遍历树,故时间复杂度O(n)。同时,需要额外的O(n)空间将树中的元素存储到链表。
Code
ArrayList<Node> treeToList(Node head){
if (head == null) return null;
ArrayList<Node> headList = new ArrayList<Node>();
Queue<Node> queue = new Queue<Node>();
queue.add(head);
queue.add(null);
ArrayList<Node> levelList = new ArrayList<Node>();
while(!queue.isEmpty()){
Node cur = queue.poll();
if (cur != null){
levelList.add(cur);
if (cur.left != null){
queue.add(cur.left);
}
if (cur.right != null){
queue.add(cur.right);
}
} else {
Node newhead = levelList.get(0);
Node backup = newhead;
for (int i = 1; i < levelList.length()-1; i++{
newhead.next = levelList.get(i);
newhead = newhead.next;
}
newhead.next = null;
headList.add(backup);
levelList.Clear();
}
}
return headList;
}