微软算法100题16 按层遍历二叉树

第16 题：
题目（微软）：
输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
例如输入
8
/
6 10
/ /
5 7 9 11
输出8 6 10 5 7 9 11

思路：遇到这种按层执行或者按次序执行的动作，一般会联想到队列

 1 package com.rui.microsoft;
 2 
 3 import java.util.ArrayDeque;
 4 import java.util.Deque;
 5 
 6 public class Test16_TraverseTreeHorizontal {
 7 
 8     public static void main(String[] args) {
 9         Node node4 = new Node(4);
10         Node node3 = new Node(3);
11         Node node5 = new Node(5);
12         Node node2 = new Node(2);
13         
14         node4.left = node3;
15         node4.right = node5;
16         node3.left = node2;
17         
18         Test16_TraverseTreeHorizontal.traverse(node4);
19     }
20     
21     public static void traverse(Node node){
22         Node head = node;
23         
24         if(null == head) return;
25         //leaf
26         if(null == head.left && null == head.right){
27             System.out.println(head.value);
28             return;
29         }
30         
31         //Non-leaf
32         Deque<Node> queue = new ArrayDeque<Node>();
33         queue.offer(head);
34         
35         while(!queue.isEmpty()){
36             Node n = queue.poll();
37             System.out.println(n.value);
38             Node left = n.left;
39             Node right = n.right;
40             if(null != left)queue.offer(left);
41             if(null != right)queue.offer(right);
42         }
43         
44     }
45     
46     static class Node{
47         int value;
48         Node left;
49         Node right;
50         Node(int v){
51             this.value = v;
52         }
53     }
54 }