题目描述

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

例如：

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

如果你不清楚“{1,#,2,3}"的含义的话，请继续阅读

我们用如下方法将二叉树序列化：

二叉树的序列化遵循层序遍历的原则，”#“代表该位置是一条路径的终结，下面不再存在结点。

例如：

上述的二叉树序列化的结果是："{1,2,3,#,#,4,#,#,5}".

public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // 借助队列进行层次遍历
        ArrayList<ArrayList<Integer>> Res = new ArrayList<ArrayList<Integer>>();//存放遍历结果
        
        Queue<TreeNode> Q = new LinkedList<TreeNode>();//创建队列
        Q.add(root);
        if(root==null){
            return Res;
        }
        while(!Q.isEmpty()){
            ArrayList<Integer> result = new ArrayList<Integer>();
            int size = Q.size();//当前队列中的元素个数(当前层)
            
            for(int i=1;i<=size;i++){ //将当前层的节点出队，并且将其相应的孩子节点出队
                TreeNode temp = Q.poll();//出队
                result.add(temp.val);
                if(temp.left!=null){
                    Q.add(temp.left);
                }
                if(temp.right!=null){
                    Q.add(temp.right);
                }
            }
            Res.add(result);//将当前层的遍历结果存放到Res
            
        }
        return Res;
    }