二叉树层序遍历

题目描述：

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

例如：

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

    3 /  9  20 / 15   7

该二叉树层序遍历的结果是

[ [3], [9,20],[15,7]]

解题思路：

使用队列，这个题与普通的层序遍历稍有不同，最后返回的结果是list的集合，每一个list是一层的遍历（从左到右）

普通的层序遍历（一个list)只需要使用队列，进出进出即可， 每出一个node将其值添加到list中，直到队列变为空。

而现在，我们需要知道每一层有多少个node，具体实现看一下代码。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        //存放最后的结果
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if(root == null){
            return result;
        }
        //借助队列先进先出的特性
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //将根入队
        queue.offer(root);
        //当队列中没有元素时遍历结束
        while(!queue.isEmpty()){
            //循环一开始，队列中第一个元素一定是某一层中最左边的元素
            //队列中的元素都是某一层的元素（从左到右）,由for循环保证
            ArrayList<Integer> b = new ArrayList<Integer>(); //存放一层数值的list
            //一层的node数量
            int levelnum = queue.size();
            //根据levelnum将一层的node出队并记录其数值，且让其左右子树进队
            for(int i = 0; i < levelnum; i++){
                //使一层中最左边的node出队，并暂存此node
                TreeNode temp = queue.poll();
                //添加node数值
                b.add(temp.val);
                //左进队
                if(temp.left != null)
                    queue.offer(temp.left);
                //右进队
                if(temp.right != null)
                    queue.offer(temp.right);
            }
            //添加一层数值的list
            result.add(b);
        }
        return result;
    }
}

代码问题：

 一开始我是在while循环之前定义了ArrayList b，在result.add(b)之后用了b.clear()，这样做会出现问题，result也清空了。