二叉树的层次遍历

题目

给定一个二叉树，返回其按层次遍历的节点值。 （即zhu'ceng'de，从左到右访问）。

例如:
给定二叉树: [3,9,20,null,null,15,7],
3
9 20
15 7
返回其层次遍历结果为：
[
[3],
[9,20],
[15,7]
]

思路

借助一个队列，将一层的所有元素都放进队列里，用变量size记录这一层有几个元素。再将它们依次弹出，记录这一层的值，同时将新它们的子节点放进队列。一直循环直到size为0，说明到达最后一层。初始化时将root放进队列，size为1。若root为null则size为0。

笔记

Queue的用法，Queue的实现类有ArrayDeque、LinkedList等。
方法：

boolean add(E e)              
boolean offer(E e)        //添加
E peek()  //取出但不删除
E poll()  //取出且删除

List<List<Integer>>如何初始化？

List<List<Integer>> list = new LinkedList<List<Integer>>();

代码

import java.util.List;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

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

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        Scanner scanner = new Scanner(System.in);

        TreeNode a = new TreeNode(3);
        TreeNode b = new TreeNode(9);
        TreeNode c = new TreeNode(20);
        TreeNode d = new TreeNode(15);
        TreeNode e = new TreeNode(7);

        a.left = b;
        a.right = c;
        b.left = null;
        b.right = null;
        c.left = d; c.right = e;
        d.left = null; d.right = null;
        e.left = null; e.right = null;

        List<List<Integer>> result = solution.levelOrder(a);
        for(List<Integer> l : result) {
            for(Integer t : l)
                System.out.print(t + "\t");
            System.out.println("\n");
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int size = 1;
        if(root == null) size = 0;

        List<List<Integer>> ans = new LinkedList<List<Integer>>();

        while(size != 0) {
            List<Integer> floor = new LinkedList<Integer>();
            int newSize = 0;
            for(int i = 0; i < size; i++) {
                TreeNode t = queue.poll();
                floor.add(t.val);
                if(t.left != null) {
                    newSize++;
                    queue.offer(t.left);
                }
                if(t.right != null) {
                    newSize++;
                    queue.offer(t.right);
                }
            }
            ans.add(floor);
            size = newSize;
        }

        return ans;
    }
}