知识卡片
队列保证树按层推进
从非空根开始入队,每次取队首访问,再把其非空左、右孩子依次入队。先进入队列的同层节点先处理,因此下一层不会越过还未处理的上一层。
每个节点访问一次,时间线性;队列峰值取决于最大层宽,保留输出还需额外n项空间。原书levelOrder未检查nil根,直接入队后解引用会失败,应把非空前提或空输入结果说清。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则,而广度优先遍历则遵循“逐层推进” 的规则,两者背后的思想是一致的。实现代码如下: // === File: binary_tree_bfs.go === /
参考来源
- 位置:《Hello 算法--Go版本》第07章《树》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/3.html;spine 2,归一字符[32177,32287))
- 结论依据:实际BFS代码入队出队/左右序及复杂度图,补充空树和输出口径。
- 原始内容:广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则,而广度优先遍历则遵循“逐层推进” 的规则,两者背后的思想是一致的。实现代码如下: // === File: binary_tree_bfs.go === /