小红使用一棵二叉树维护大模型服务的容器镜像层。每个节点保存当前层带来的大小变化,正数表示新增文件,负数表示删除文件。一个节点的完整镜像大小,等于从根节点到该节点路径上所有节点值之和。 小红需要依次执行以下整理规则: 1. 如果某个节点的完整镜像大小小于或等于 0 ,则该节点异常,需要连同它的整棵子树一起删除。 2. 完成所有异常节点的删除后,如果一个节点恰好只有一个子节点,则将这两个节点合并。合并后的节点占据原父节点的位置,节点值为二者之和,并继承原子节点的子树。只要仍存在恰好只有一个子节点的节点,就继续执行合并。 输入给出原二叉树的前序遍历和中序遍历。所有原始节点值互不相同,因此能够唯一还原二叉树。请输出整理后树的后序遍历。
第一行输入若干个整数,表示原二叉树的前序遍历。 第二行输入相同数量的整数,表示原二叉树的中序遍历。 保证节点数不超过 1000 ,每个原始节点值在 [-10000,10000] 内,并且所有节点值互不相同。
输出整理后树的后序遍历,整数之间用一个空格分隔。如果整理后的树为空,则输出字符串 null。
5 2 -3 4 2 5 -3 4
2 1 5
考点:树
限制 1 秒 / 256MB | 标准输入输出
参考方向:树
树结构上的遍历(DFS 求子树信息 / BFS 求层序),多数树题是「后序遍历 + 回溯」。
思路框架(树 通法 · 非本题专属)
实现要点:递归深度可能到 1e5,注意递归爆栈;必要时改迭代或调整递归深度。
复杂度:时间 O(n) | 空间 O(n)
该范式的通法易错点
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。
样例 1:输入 5 2 -3 4 / 2 5 -3 4 → 输出 2 1 5
值为 -3 的节点只有一个值为 4 的子节点,合并后节点值为 1 。
解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:2026年-华为-05月20号开发岗。