知识卡片
前中序重建依赖互异合法输入
前序首项给出当前根,在中序中找到它,便确定左右子树的元素数量与范围,再按这些数量切分前序子区间递归建立两侧。哈希索引可避免每层重新线性寻找根。
要求值互异、两序列包含同一组元素且确实来自同一合法树,子树不一定等大。原书直接读取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 的划分结果,易得左子树和右子树的节点数量分