[剑指offer][JAVA]面试题第[32-1]题[从上到下打印二叉树][BFS]

【问题描述】[中等]

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。例如:给定二叉树: [3,9,20,null,null,15,7],3/ \9 20/ \15 7返回：[3,9,20,15,7]

【解答思路】

BFS

时间复杂度：O(N) 空间复杂度：O(N)

class Solution {public int[] levelOrder(TreeNode root) {if(root == null) return new int[0];// Queue<TreeNode> queue= new LinkedList<>();//queue.add(root);Queue<TreeNode> queue = new LinkedList<>(){{add(root); }};ArrayList<Integer> ans = new ArrayList<>();while(!queue.isEmpty()) {TreeNode node = queue.poll();ans.add(node.val);if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}int[] res = new int[ans.size()];for(int i = 0; i < ans.size(); i++)res[i] = ans.get(i);return res;}}

【总结】

1.细节

1.1 Queue

新建

// Queue<TreeNode> queue= new LinkedList<>();//queue.add(root);Queue<TreeNode> queue = new LinkedList<>(){{add(root); }};

入队出队 add(x) poll()

1.2 ArrayList

新建

ArrayList ans = new ArrayList<>();

长度 size（）

获取元素 get(i)

2. Queue

Queue是在两端出入的List，所以也可以用数组或链表来实现。

add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常offer 添加一个元素并返回true 如果队列已满，则返回falsepoll 移除并返问队列头部的元素 如果队列为空，则返回nullpeek 返回队列头部的元素 如果队列为空，则返回nullput 添加一个元素 如果队列满，则阻塞take 移除并返回队列头部的元素 如果队列为空，则阻塞

注意

remove、element、offer 、poll、peek 其实是属于Queue接口。

add remove element操作在队满或者队空的时候会报异常。

offer poll peek 在队满或者队空的时候不会报异常。

put take操作属于阻塞操作。队满队空均会阻塞。

3.LinkedList

以双向链表实现的LinkedList既是List，也是Queue。它是唯一一个允许放入null的Queue。

4.BFS 层次遍历 队列实现

转载链接：https://leetcode-/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/solution/mian-shi-ti-32-i-cong-shang-dao-xia-da-yin-er-ch-4/