东莞免费建站模板,网站的图片怎么做,论文网站建设格式,深圳H5网站开发【问题描述】[中等]
从上到下打印出二叉树的每个节点#xff0c;同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],3/ \9 20/ \15 7
返回#xff1a;[3,9,20,15,7]【解答思路】
BFS 时间复杂度#xff1a;O(N) 空间复杂度#xff1a…【问题描述】[中等]
从上到下打印出二叉树的每个节点同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [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];// QueueTreeNode queue new LinkedList();//queue.add(root);QueueTreeNode queue new LinkedList(){{ add(root); }};ArrayListInteger 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 新建 // QueueTreeNode queue new LinkedList();//queue.add(root);QueueTreeNode 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-cn.com/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/
