本题需要根据二叉树的前序遍历和中序遍历还原原树,然后按规则简化树,最后输出后序遍历。
核心算法包括:二叉树重建、深度优先搜索、路径和剪枝、链式节点合并。
具体做法:
先用前序遍历和中序遍历重建二叉树。前序遍历的第1个值一定是当前子树根节点,在中序遍历中找到根节点位置后,可以确定左子树和右子树范围。
在容器镜像管理系统中,容器镜像通常采用堆叠方式管理和挂载。为了减少镜像管理系统中重复的镜像层数量,假定容器镜像采用二叉树管理。镜像层二叉树节点描述镜像层大小,节点的镜像完整大小为镜像层大小及其所有父镜像层大小之和。当前需要对镜像管理系统中的镜像二叉树进行整理,整理过程必须满足如下规则:
输入为容器镜像二叉树前序遍历数组和中序遍历数组,输出为镜像树简化后的后序遍历数组。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.