小红正在分析一个用于智能体推理的决策树。树上的每个节点都记录了一个整数分值,表示模型在这一层做出某个选择时带来的偏移量。 如果一条路径同时满足下面三个条件,小红就把它称为一条平衡路径: 1. 路径可以从树中的任意节点开始; 2. 从起点出发后,每一步都只能走向当前节点的左子节点或右子节点,也就是说整条路径必须始终向下延伸,不能回到父节点,也不能分叉; 3. 路径上所有节点的分值之和恰好为 0,并且这条路径包含的节点个数至少为 2。 现在给定这棵二叉树的层序遍历结果,请你帮助小红统计这棵树中一共有多少条平衡路径。
输入描述:
第一行一个整数 `n`,表示层序遍历列表中的元素个数,`1 第二行给出 `n` 个元素,按从上到下、从左到右的顺序描述这棵树。每个元素要么是一个整数,表示对应节点的分值;要么是字符串 `None`,表示该位置为空。保证第一个元素不是 `None`,非空节点的分值满足 `-10^9 建树时采用常见的层序规则:每次从队列中取出一个非空节点,再按顺序读取它的左孩子和右孩子;如果某个孩子为 `None`,则对应位置不建立节点。


输出描述:
输出一个整数,表示平衡路径的总数。 注意答案可能超过 32 位整数范围。
示例1

输入

3
0 0 0

输出

2

说明

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