知识卡片
深度遍历按访问时点分三序
深度优先沿一条分支深入,完成后返回再走另一分支。前序在左右子树之前访问根,中序在两子树之间访问根,后序在两子树之后访问根。
差别是同一递归结构中的访问时点,不是三种完全无关路径。调用栈辅助空间与高度相关,最坏可线性;若保存完整遍历序列,还需计输出。原书全局nums在多次调用前应重置,也不能无同步并发写入。
后序代码先完成左、右递归,再记录根;三序都可通过同一递归框架表达。遍历整体访问n个节点为线性时间,辅助栈按高度计,若树退化则线性,不把输出序列和辅助栈混算。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
“先走到尽头,再回溯继续”的遍历方式。 图7‑10 展示了对二叉树进行深度优先遍历的工作原理。 深度优先遍历就像是绕着整棵二叉树的外围“走”一 圈 ,在每个节点都会遇到三个位置,分别对应前序遍历、中序遍历和后序遍历。 第
- · 查看原书依据
func postOrder(node *TreeNode) { if node == nil { return } // 访问优先级:左子树 postOrder(node.Left ) postOrder(node.R
参考来源
- 位置:《Hello 算法--Go版本》第07章《树》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/3.html;spine 2,归一字符[32938,33048))
- 结论依据:实际三序定义、图7-10和preOrder/inOrder代码支持访问时点,后序在下一段续完。
- 原始内容:“先走到尽头,再回溯继续”的遍历方式。 图7‑10 展示了对二叉树进行深度优先遍历的工作原理。 深度优先遍历就像是绕着整棵二叉树的外围“走”一 圈 ,在每个节点都会遇到三个位置,分别对应前序遍历、中序遍历和后序遍历。 第
补充原书证据:spine 3 / extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/4.html;归一字符[37,147)。
- 结论依据:实际后序收尾与递归图补全前段访问时点。
- 原始内容:func postOrder(node *TreeNode) { if node == nil { return } // 访问优先级:左子树 postOrder(node.Left ) postOrder(node.R