华为 · 树 · 算法编程题
华为 时限 1 秒 / 256 MB

题目描述

小红使用一棵二叉树维护大模型服务的容器镜像层。每个节点保存当前层带来的大小变化,正数表示新增文件,负数表示删除文件。一个节点的完整镜像大小,等于从根节点到该节点路径上所有节点值之和。
小红需要依次执行以下整理规则:
1. 如果某个节点的完整镜像大小小于或等于 0 ,则该节点异常,需要连同它的整棵子树一起删除。
2. 完成所有异常节点的删除后,如果一个节点恰好只有一个子节点,则将这两个节点合并。合并后的节点占据原父节点的位置,节点值为二者之和,并继承原子节点的子树。只要仍存在恰好只有一个子节点的节点,就继续执行合并。
输入给出原二叉树的前序遍历和中序遍历。所有原始节点值互不相同,因此能够唯一还原二叉树。请输出整理后树的后序遍历。

输入输出

输入描述
第一行输入若干个整数,表示原二叉树的前序遍历。
第二行输入相同数量的整数,表示原二叉树的中序遍历。
保证节点数不超过 1000 ,每个原始节点值在 [-10000,10000] 内,并且所有节点值互不相同。
输出描述
输出整理后树的后序遍历,整数之间用一个空格分隔。如果整理后的树为空,则输出字符串 null。

样例共 1 组

样例 1 · 值为 -3 的节点只有一个值为 4 的子节点,合并后节点值为 1 。
输入
5 2 -3 4
2 5 -3 4
输出
2 1 5

算法解析依据一般

考点:树

限制 1 秒 / 256MB | 标准输入输出

题目画像

  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

参考方向:树

树结构上的遍历(DFS 求子树信息 / BFS 求层序),多数树题是「后序遍历 + 回溯」。

思路框架(树 通法 · 非本题专属)

  1. 按输入建图(父子关系一般给父节点编号,孩子用邻接表存)。
  2. 确定遍历方式:自底向上合并子树信息(后序 DFS)或自顶向下传参(前序 DFS)。
  3. 对每个节点,用孩子的答案合并出当前节点的答案。
  4. 涉及层间操作(如层序变换)时用 BFS 逐层处理。

实现要点:递归深度可能到 1e5,注意递归爆栈;必要时改迭代或调整递归深度。

复杂度:时间 O(n) | 空间 O(n)

该范式的通法易错点

  • 递归深度过大导致爆栈。
  • 建树时父子关系方向搞反(把树当成有向图但遍历方向错)。
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。

样例解读

样例 1:输入 5 2 -3 4 / 2 5 -3 4 → 输出 2 1 5

值为 -3 的节点只有一个值为 4 的子节点,合并后节点值为 1 。

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:2026年-华为-05月20号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解