二叉树层次遍历（剑指Offer面试题32：从上到下打印二叉树）

图1所示为二叉树的层次遍历，即按照箭头所指方向，按照1、2、3的层次顺序，对二叉树每个节点进行访问

（此图反映的是自左至右的层次遍历，自右至左的方式类似）。

要进行层次遍历，需要建立一个队列。先将二叉树头节点入队列，然后出队列，访问该节点，

如果它有左子树，则将左子树的根结点入队；如果它有右子树，则将右子树的根结点入队。然后出队列，对出队节点访问，

如此反复直到队列为空为止。

 1 import java.util.*;
 2 class TreeNode
 3 {
 4     int val;
 5     TreeNode left;
 6     TreeNode right;
 7     TreeNode(int val) {
 8         this.val=val;
 9     }
10 }
11 class Solution 
12 {
13     public void level(TreeNode head) {
14         Queue<TreeNode> queue=new LinkedList<TreeNode>();
15         if(head!=null) {
16             queue.offer(head);
17             while(queue.size()!=0) {
18                 TreeNode node=queue.poll();
19                 System.out.println(node.val);
20                 if(node.left!=null) {
21                     queue.offer(node.left);
22                 }
23                 if(node.right!=null) {
24                     queue.offer(node.right);
25                 }
26             }
27         }
28     }
29     public static void main(String[] args) {
30         Solution s=new Solution();
31         TreeNode head=new TreeNode(1);
32         head.left=new TreeNode(3);
33         head.right=new TreeNode(4);
34         head.left.left=new TreeNode(6);
35         head.left.right=new TreeNode(5);
36         s.level(head);
37     }
38     
39 }

剑指Offer 面试题32：

题目描述：

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

以下为测试通过程序：

 1 import java.util.*;
 2 /**
 3 public class TreeNode {
 4     int val = 0;
 5     TreeNode left = null;
 6     TreeNode right = null;
 7 
 8     public TreeNode(int val) {
 9         this.val = val;
10 
11     }
12 
13 }
14 */
15 class Solution 
16 {
17     public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
18         Queue<TreeNode> queue=new LinkedList<TreeNode>();
19         ArrayList<Integer> list=new ArrayList<Integer>();
20 
21         if(root!=null) {
22             queue.offer(root);
23             while(queue.size()!=0) {
24                 TreeNode node=queue.poll();
25                 list.add(node.val);
26                 if(node.left!=null) {
27                     queue.offer(node.left);
28                 }
29                 if(node.right!=null) {
30                     queue.offer(node.right);
31                 }
32             }
33         }
34         return list;
35     }
36 }

欢迎评论！！