第一个做电子商务的网站,工信部网站 备案,个人业务网站创建,wordpress优秀模板【问题描述】[简单] 从上到下按层打印二叉树#xff0c;同一层的节点按从左到右的顺序打印#xff0c;每一层打印到一行。例如:
给定二叉树: [3,9,20,null,null,15,7],3/ \9 20/ \15 7
返回其层次遍历结果#xff1a;[[3],[9,20],[15,7]
]【解答思路】
层次遍历 BFS 时…【问题描述】[简单] 从上到下按层打印二叉树同一层的节点按从左到右的顺序打印每一层打印到一行。例如:
给定二叉树: [3,9,20,null,null,15,7],3/ \9 20/ \15 7
返回其层次遍历结果[[3],[9,20],[15,7]
]
【解答思路】
层次遍历 BFS 时间复杂度O(N) 空间复杂度O(N) public ListListInteger levelOrder(TreeNode root) {QueueTreeNode queue new LinkedList();//与32-1 不同之处ListListInteger res new ArrayList();if(root ! null){queue.add(root);}while(!queue.isEmpty()) {ListInteger tmp new ArrayList();for(int iqueue.size(); i0;i-- ){TreeNode node queue.poll();tmp.add(node.val);if(node.left!null){queue.add(node.left);}if(node.right!null){queue.add(node.right);}}res.add(tmp);}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-ii-lcof/solution/mian-shi-ti-32-ii-cong-shang-dao-xia-da-yin-er-c-5/
