根据前序遍历和中序遍历可以唯一还原二叉树。
前序遍历的第一个节点一定是当前子树根节点,利用中序遍历中根节点的位置,可以划分出左子树和右子树。
本题不需要真正建树,可以在递归还原子树的过程中,直接计算每个节点的完整镜像大小。
设当前节点的父节点完整镜像大小为 parentSum,当前节点镜像层大小为 val,则当前节点完整镜像大小为:
在容器镜像管理系统中,镜像层按照二叉树结构堆叠管理。树中每个节点表示一个镜像层,节点的数值称为该节点的镜像层大小,表示该层相对父层新增或裁剪的数据量。
对于某个节点,定义其镜像完整大小为从根节点到该节点路径上所有节点的镜像层大小之和,也就是自身镜像层大小加上所有父镜像层大小之和。
现给定一棵镜像层二叉树的前序遍历和中序遍历结果,要求统计剪枝后所有保留节点的镜像完整大小的平均值。平均值需要忽略小数部分并向下取整。
如果某个节点的镜像完整大小小于等于 0,则该节点为异常节点。异常节点需要剪枝,并且以该节点为根的整棵子树都会被删除。例如,节点 A 有子节点 B 和 C,若 A 的镜像完整大小为 0,则 A、B、C 都会被移除,不参与统计。
约束条件
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册