知识卡片

普通读书笔记卡 · 5654.d.1.a.1.c.1.d.2

队列保证树按层推进

理解等级:中级

从非空根开始入队,每次取队首访问,再把其非空左、右孩子依次入队。先进入队列的同层节点先处理,因此下一层不会越过还未处理的上一层。

每个节点访问一次,时间线性;队列峰值取决于最大层宽,保留输出还需额外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 === /