根据前序遍历和中序遍历可以唯一还原二叉树。
前序遍历的第一个节点一定是当前子树根节点,利用中序遍历中根节点的位置,可以划分出左子树和右子树。
本题不需要真正建树,可以在递归还原子树的过程中,直接计算每个节点的完整镜像大小。
设当前节点的父节点完整镜像大小为 parentSum,当前节点镜像层大小为 val,则当前节点完整镜像大小为:
在容器镜像管理系统中,容器镜像通常采用堆叠方式管理和挂载,为了减少镜像管理系统中重复的存储量,假定容器镜像层采用二叉树管理。镜像层二叉树节点描述镜像层大小,节点的镜像完整大小为镜像层大小及其所有父镜像层大小之和。由于业务需要,现在需要对系统中所有的客户镜像大小统计分析,统计镜像平均大小:输入为容器镜像二叉树前序遍历数组和中序遍历数组,输出为平均镜像大小,输出结果忽略小数并向下取整。
说明:当镜像完整大小小于等于 0 时,则表示该镜像节点异常,异常镜像节点需要剪枝;例如:节点 A 有子节点 B 和子节点 C,如果节点 A 完整镜像大小为 0,则节点 A 需要剪枝,即节点 A、节点 B、节点 C 均需要从镜像二叉树中删除。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册