题目

解题思路

1、BFS 广度优先搜索

BFS 通常借助 队列 的先入先出特性来实现。

实现

1、BFS 广度优先搜索

class Solution {
    public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        // 记录顺序
        ArrayList<Integer> answer = new ArrayList<>();
        // 借助队列实现BFS
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            // poll 将队首从队列中弹出，如果队列是空的，就返回null
            TreeNode node = queue.poll();
            answer.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        // 生成 int 数组
        int[] result = new int[answer.size()];
        for (int i = 0; i < answer.size(); i++) {
            result[i] = answer.get(i);
        }
        return result;
    }
}