Binary Tree Level Order Traversal LeetCode

题目

https://leetcode.com/problems/binary-tree-level-order-traversal/description/

思路

很明显的广度优先遍历，使用队列保存入队元素，当遍历一个节点时，先把父节点入队，然后依次是左孩子节点和右孩子节点，由于队列的现金先出，所以出队，就可以 一层一层的输出树中的元素。

但是这个题目的难度在于你怎么把一层的节点值放到不同的list中去。这里看到有一个方法：
定义一个变量levelNum，用来表示树中每层的元素的个数，最开始时levelNum = 1(若root != null)，然后每层做levelNum次循环，把每层的下一层的所有节点入队，同时把这一层的levelNum个元素放到一个新的list中去。

代码

public class LC_102_Binary_Tree_Level_Order_Traversal {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int x){
            val = x;
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<List<Integer>>(); 
        if(root == null)
            return null;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            int levelNum = queue.size();
            List<Integer> list =  new ArrayList<Integer>();
            for(int i = 0; i < levelNum; i++){
                TreeNode node = queue.peek();
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
                list.add(queue.poll().val);
            }
            lists.add(list);
        }
        return lists;
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

    }

}