← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 5654.c.3.e.2

前中序重建依赖互异合法输入

理解等级:中级

前序首项给出当前根,在中序中找到它,便确定左右子树的元素数量与范围,再按这些数量切分前序子区间递归建立两侧。哈希索引可避免每层重新线性寻找根。

要求值互异、两序列包含同一组元素且确实来自同一合法树,子树不一定等大。原书直接读取map缺失键会得到默认0,不能据此接受非法输入;还须校验索引范围和前序长度,空区间返回nil。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      前序遍历的首元素3 是根节点的值。 2. 查找根节点3 在inorder 中的索引,利用该索引可将inorder 划分为[ 9 | 3 1 2 7 ] 3. 根据inorder 的划分结果,易得左子树和右子树的节点数量分

    参考来源

    - 位置:《Hello 算法--Go版本》第12章《分治》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/6.html;spine 5,归一字符[15075,15185)) - 结论依据:实际根定位/区间i+1+m-l/哈希映射及代码,保留合法性前提。 - 原始内容:前序遍历的首元素3 是根节点的值。 2. 查找根节点3 在inorder 中的索引,利用该索引可将inorder 划分为[ 9 | 3 1 2 7 ] 3. 根据inorder 的划分结果,易得左子树和右子树的节点数量分