LeetCode C++ 面试题 04.03. List of Depth LCCI【Tree/BFS】中等
发布日期:2021-07-01 02:57:01
浏览次数:2
分类:技术文章
本文共 1181 字,大约阅读时间需要 3 分钟。
Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D
, you’ll have D
linked lists). Return a array containing all the linked lists.
Example:
Input: [1,2,3,4,5,null,7,8] 1 / \ 2 3 / \ \ 4 5 7 / 8Output: [[1],[2,3],[4,5,7],[8]]
题意:给定一棵二叉树,对每一深度上的所有节点分别创建链表,返回一个包含所有深度的链表的数组。
解法 BFS
class Solution { public: vectorlistOfDepth(TreeNode* tree) { if (tree == nullptr) return { }; vector ans; queue q; q.push(tree); while (!q.empty()) { int size = q.size(); ListNode dummy(0), *rear = &dummy; //虚拟头结点+尾插法 for (int i = 0; i < size; ++i) { TreeNode *t = q.front(); q.pop(); rear->next = new ListNode(t->val); rear = rear->next; if (t->left) q.push(t->left); if (t->right) q.push(t->right); } ans.push_back(dummy.next); } return ans; }};
执行结果如下:
执行用时:4 ms, 在所有 C++ 提交中击败了68.22% 的用户内存消耗:8.4 MB, 在所有 C++ 提交中击败了29.59% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/110103633 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月26日 16时55分46秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
ImageView scaleType
2019-05-01
RecyclerView notifyItem闪屏问题
2019-05-01
dubbo学习笔记 十一 dubbo-rpc之模块
2019-05-01
motan学习笔记 五 opentracing学习入门
2019-05-01
求列表最长子序列
2019-05-01
字符串的排序
2019-05-01
内存分配(mallloc,calloc,realloc,new)
2019-05-01
网络编程之 Socket函数 (二)
2019-05-01
网络编程之 Socket的模式(一) --- “阻塞/非阻塞” 与 “同步/异步”
2019-05-01
ffmpeg & mplayer & vlc 手册
2019-05-01
Go语言并发组件
2019-05-01
简析STUN协议
2019-05-01
使用 Minidumps 和 Visual Studio .NET 进行崩溃后调试
2019-05-01
Debug 和 Release 编译方式的本质区别
2019-05-01
struts返回xml数据例子
2019-05-01
内存对齐详解
2019-05-01
秋招总结(一)-C++归纳
2019-05-01
秋招总结(三)-操作系统归纳
2019-05-01
带缓冲I/O 和不带缓冲I/O的区别与联系
2019-05-01
LINUX CP命令详解
2019-05-01