Leetcode038--二叉树的层序遍历

一、原题

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level). For example: Given binary tree {3,9,20,#,#,15,7},

    3   / /  9  20    /  /   15   71234512345
return its level order traversal as:
[  [3],  [9,20],  [15,7]]
一、中文
给定一个二叉树，输出它的每一层的结点。
三、举例
上面的题目中给的就有例子，还是比较好理解的
四、思路
 使用两个队列的方式，队列是先进先出的，所以我们这里使用两个队列，一个队列存储当前层的二叉树结点，另外一个队列来存储下一层的结点，然后将当前层的左右子结点按照顺序放入下一层中，处理完下一层之后将本层和下一层进行一个互换的操作。
五、程序
package code;import java.util.Deque;import java.util.Iterator;import java.util.LinkedList;//class TreeNode{//	int val;//	TreeNode left;//	TreeNode right;//	TreeNode(int x){//		val = x;//	}//}public class LeetCode51{	public static void main(String args[]){		TreeNode n1 = new TreeNode(1);		TreeNode n2 = new TreeNode(2);		TreeNode n3 = new TreeNode(2);		TreeNode n4 = new TreeNode(3);		TreeNode n5 = new TreeNode(4);		TreeNode n6 = new TreeNode(3);		TreeNode n7 = new TreeNode(4);				n1.left = n2;		n1.right = n3;				n2.left = n4;		n2.right = n5;				n3.left = n7;		n3.right = n6;				LinkedList<LinkedList<Integer>> res = levelOrder(n1);				Iterator<LinkedList<Integer>> it1 = res.iterator();		while(it1.hasNext()){			Iterator<Integer> it2 = it1.next().iterator();			while(it2.hasNext()){				System.out.PRint(it2.next()+" ");			}			System.out.println();		}	}	//第一种使用递归的方式	public static LinkedList<LinkedList<Integer>> levelOrder(TreeNode root) {		LinkedList<LinkedList<Integer>> res = new LinkedList<>();				if(root == null){			return res;		}		        Deque<TreeNode> cur = new LinkedList<>();        Deque<TreeNode> sub = new LinkedList<>();        Deque<TreeNode> exc;                cur.addLast(root);        TreeNode node;                while(!cur.isEmpty()){        	LinkedList<Integer> temp = new LinkedList<>();        	        	while(!cur.isEmpty()){        		node = cur.removeFirst();        		temp.add(node.val);        		        		if(node.left != null){        			sub.addLast(node.left);	        		}        		        		if(node.right != null){        			sub.addLast(node.right);	        		}        		        	}        	    		exc = cur;            cur = sub;            sub = exc;            res.add(temp);        }        return res;	}	}	----------------------------------------output-------------------------------------------
1 2 2 3 4 4 3