题目内容

给定一棵二叉树，根节点记为 root，同时给出一个整数 target。二叉树按照层序规则构造：从根节点开始，自上而下、从左到右依次放置节点。

一条路径从树中任意一个节点出发，最终必须到达一个叶子节点。叶子节点定义为没有左孩子且没有右孩子的节点。

对于路径上依次经过的节点 $p_1, p_2, p_3, \ldots$，如果 $p_2$ 是 $p_1$ 的左孩子，则 $p_3$ 必须是 $p_2$ 的右孩子；如果 $p_2$ 是 $p_1$ 的右孩子，则 $p_3$ 必须是 $p_2$ 的左孩子。后续节点也按照“左、右、左……”或“右、左、右……”的方向严格交替选择。满足这一方向交替规则的路径称为之字形路径。一条之字形路径必须至少包含 3 个节点，否则不纳入统计。

路径和定义为路径中全部节点值的总和。请统计所有之字形路径中，路径和恰好等于 target 的路径条数。

约束条件：

• 层序数组的长度大于 0 且不超过 1024。
• 层序数组中表示节点存在的值均为非负整数，-1 仅用于标记空节点。
• target 的取值范围为 0 到 10000，包含两端。

输入描述

输入共三行。 第一行包含一个整数 n，表示接下来给出的层序数组长度。 第二行包含 n 个整数，表示二叉树的层序数组，其中 -1 表示该位置不存在节点。 第三行包含一个整数 target，表示需要匹配的路径和。

输出描述

输出一个整数，表示路径和等于 target 的之字形路径条数；如果没有任何满足条件的路径，则输出 -1。

样例1

输入

5
1 2 -1 -1 3
6

输出

1

说明

树的结构如图：

从根节点出发，先向左到达 2，随后按交替规则向右到达 3，形成路径 $1 \to 2 \to 3$。该路径包含 3 个节点，路径和为 $1+2+3=6$，恰好等于目标 6。

从其他节点出发时，没有其他长度至少为 3 且路径和为 6 的之字形路径，因此总数为 1。

样例2

输入

7
0 1 2 -1 5 4 -1
6

输出

2

说明

树的结构如图：

从根节点出发，先向左到达 1，再向右到达 5，路径为 $0 \to 1 \to 5$，长度为 3，路径和为 $0+1+5=6$。从根节点出发，先向右到达 2，再向左到达 4，路径为 $0 \to 2 \to 4$，长度同样为 3，路径和为 $0+2+4=6$。

这两条路径都满足之字形规则且路径和等于目标 6，没有其他满足条件的路径，因此总数为 2。

样例3

输入

1
7
10

输出

-1

说明

树中只有一个值为 7 的节点，没有任何左右孩子。

由于之字形路径必须至少包含 3 个节点，单节点无法形成有效路径，统计数量为 0，按要求输出 -1。

样例4

输入

63
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
5

输出

30

说明

这个用例为5层的满二叉中，其中第 1～5 层的所有非叶子节点值均为 0，最后一层的 32 个叶子节点值全部为 5。因此，只要一条之字形路径最终到达叶子，它的路径和就是 5，恰好等于 target。

树一共有 6 层，也就是根节点位于深度 0，叶子节点位于深度 5。由于路径至少需要包含 3 个节点，因此起点最多只能位于深度 3。

各层作为起点能够产生的合法路径数为：

所以总数为

这里每个深度 0~3 的节点都有两种走法：第一次向左，之后按照 左→右→左→右…… 交替；或者第一次向右，之后按照 右→左→右→左…… 交替。满二叉树保证这两种走法最终都能到达叶子，因此预期输出就是 30。