Binary Tree Level Order Traversal
二叉树的层序遍历
两种方式：
1、用两个queue交替表示每一层的节点
2、用两个node，一个表示当前层的最后一个节点，一个表示下一层的最后一个节点
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.Queue;
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
if(root == null)
return list;
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
Queue<TreeNode> queue2 = new ArrayDeque<TreeNode>();
queue.offer(root);
List<Integer> listLevel = new ArrayList<Integer>();
TreeNode curNode = null;
while( !queue.isEmpty() || (!queue2.isEmpty())) {
while(!queue.isEmpty()){
curNode = queue.poll();
listLevel.add(curNode.val);
if(curNode.left != null) queue2.offer(curNode.left);
if(curNode.right != null) queue2.offer(curNode.right);
if(queue.isEmpty()){
list.add(listLevel);
listLevel = new ArrayList<Integer>();
}
}
while(!queue2.isEmpty()){
curNode = queue2.poll();
listLevel.add(curNode.val);
if(curNode.left != null) queue.offer(curNode.left);
if(curNode.right != null) queue.offer(curNode.right);
if(queue2.isEmpty()){
list.add(listLevel);
listLevel = new ArrayList<Integer>();
}
}
}
/** 两个node，
* lastNode: 当前层的最后一个节点
* lastInqueue:表示某层最后进入队列的节点
TreeNode curNode = root;
TreeNode lastNode = root;
TreeNode lastInQueue = root;
while(!queue.isEmpty()){
curNode = queue.poll();
listLevel.add(curNode.val);
if(curNode.left != null){
queue.offer(curNode.left);
lastInQueue = curNode.left;
}
if(curNode.right != null){
queue.offer(curNode.right);
lastInQueue = curNode.right;
}
if(curNode == lastNode){
list.add(listLevel);
// get last node
lastNode = lastInQueue;
listLevel = new ArrayList<Integer>();
}
}
*/
return list;
}
}