java版：层序遍历

描述

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）

例如：

给定的二叉树是{3,9,20,#,#,15,7},

该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]
]

示例1
输入：
{1,2}

返回值：
[[1],[2]]

示例2
输入：
{1,2,3,4,#,#,5}

返回值：
[[1],[2,3],[4,5]]

解题思路：

层序遍历：

• 就是从根节点（第一层）开始，依次向下，获取每一层所有结点的值，有二叉树如下：

实现步骤：

• 1.创建队列，存储每一层的结点；
• 2.使用循环从队列中弹出一个结点：
• 3.获取当前结点的key；
• 4.如果当前结点的左子结点不为空，则把左子结点放入到队列中
• 5.如果当前结点的右子结点不为空，则把右子结点放入到队列中

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    //[[1],[2,3],[4,5]]
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        //根节点为空，直接返回res
        if(root == null)
            return res;
        if(root !=null){
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                int size = queue.size();
                ArrayList<Integer> level = new ArrayList<Integer>();
                while(size-->0){
                    TreeNode temp = queue.poll();
                    level.add(temp.val);
                    if(temp.left!=null)
                        queue.offer(temp.left);
                    if(temp.right!=null)
                        queue.offer(temp.right);
                }
                res.add(level);
            }
        }
        return res;        
    }
}