牛客题解-NC15求二叉树的层序遍历

发表于 更新于 分类于 阅读次数：

题目

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历） 例如： 给定的二叉树是{3,9,20,#,#,15,7},

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

示例1

输入：

1
{1,2}

输出：

1
[[1],[2]]

示例2

输入：

1
{1,2,3,4,#,#,5}

输出：

1
[[1],[2,3],[4,5]]

思路

分析

bfs问题借助队列FIFO的特性。

逐层遍历二叉树，在某一层进行遍历的时候。写入遍历信息到ArrayList集合中去的同时，判断每个节点是否存在左右子树。存在的话将对应的子节点入队。以准备下一层次的遍历。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            ArrayList<Integer> level = new ArrayList<>();
            int len = queue.size();
            for(int i = 0; i<len; i++){
                TreeNode tmp = queue.poll();
                level.add(tmp.val);
                if(tmp.left != null) queue.offer(tmp.left);
                if(tmp.right != null) queue.offer(tmp.right);
            }
            res.add(level);
        }
        return res;
    }
}