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

题目描述

小红正在分析一个用于智能体推理的决策树。树上的每个节点都记录了一个整数分值,表示模型在这一层做出某个选择时带来的偏移量。
如果一条路径同时满足下面三个条件,小红就把它称为一条平衡路径:
1. 路径可以从树中的任意节点开始;
2. 从起点出发后,每一步都只能走向当前节点的左子节点或右子节点,也就是说整条路径必须始终向下延伸,不能回到父节点,也不能分叉;
3. 路径上所有节点的分值之和恰好为 0,并且这条路径包含的节点个数至少为 2。
现在给定这棵二叉树的层序遍历结果,请你帮助小红统计这棵树中一共有多少条平衡路径。

输入输出

输入描述
第一行一个整数 `n`,表示层序遍历列表中的元素个数,`1
第二行给出 `n` 个元素,按从上到下、从左到右的顺序描述这棵树。每个元素要么是一个整数,表示对应节点的分值;要么是字符串 `None`,表示该位置为空。保证第一个元素不是 `None`,非空节点的分值满足 `-10^9
建树时采用常见的层序规则:每次从队列中取出一个非空节点,再按顺序读取它的左孩子和右孩子;如果某个孩子为 `None`,则对应位置不建立节点。
输出描述
输出一个整数,表示平衡路径的总数。
注意答案可能超过 32 位整数范围。

样例共 1 组

样例 1 · 这棵树的根节点有两个孩子,且它们的分值都为 0。以根节点为起点向左走可以得到一条长度为 2 的路径,节点和为 0;向右走同样满足条件,所以答案是 2。
输入
3
0 0 0
输出
2

算法解析依据一般

考点:树

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

题目画像

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

解题思路

参考方向:树

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

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

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

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

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

该范式的通法易错点

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

样例解读

样例 1:输入 3 / 0 0 0 → 输出 2

这棵树的根节点有两个孩子,且它们的分值都为 0。以根节点为起点向左走可以得到一条长度为 2 的路径,节点和为 0;向右走同样满足条件,所以答案是 2。

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

本题来源:2026年-华为-04月22号AI岗。

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