102. Binary Tree Level Order Traversal Java Solutions

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,null,null,15,7],     3    / \   9  20     /  \    15   7 return its level order traversal as: [   [3],   [9,20],   [15,7] ] 问题：进行层次遍历，输出要求每层分层输出 思想：分层遍历是借助队列来实现的，当队不为空，出队并对该元素进行检查，如果有左右孩子将孩子入队，重复以上步骤 此题关键点在于如何划分队列中的元素属于不同层，所以借助int size=q.size(),以size表示该层有几个节点，那么就要循环遍历这些点 看它们是否有孩子

如果有将孩子入队，此时队列大小q.size会改变，但是size还是上一层的大小，直到size==0后，循环结束size=新的q.size

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> levelOrder(TreeNode root) { // if(root==null) return new ArrayList<List<Integer>>(null); List<List<Integer>> result=new ArrayList<List<Integer>>(); if(root==null) return result; Queue<TreeNode> q=new LinkedList(); q.add(root); while(!q.isEmpty()){ List<Integer> levelList=new ArrayList(); int size=q.size();//******这里是保证每层节点为一组添加到levelList在添加到result中 for(int i=0;i<size;i++){ TreeNode node=q.poll(); levelList.add(node.val); if(node.left!=null) q.add(node.left);//将左右孩子添加到队列中，q.size会改变，但for循环中的size仍为上一层时的大小 if(node.right!=null) q.add(node.right); } result.add(levelList); } return result; } }