解题思路

• 按题意，数组按层序（从上到下一层、从左到右）构造二叉树，-1 表示该位置为空节点。

• “路径”定义：从任意节点出发一直向下到叶子的节点序列；“之字形路径”要求边方向左右交替（或右左交替），并且至少包含 3 个节点。

• 做法：

  1. 先用队列按层序把树建出来。
  2. 枚举树中每个节点作为起点，各尝试两种首步方向：先向左或先向右。
  3. 之后沿着唯一确定的交替方向继续向下直到无法前进；只有到达叶子且长度≥3 才判定为一条合法路径，累加路径和与目标值比较。

题目内容

给定一个二叉树根节点 $root$ 和一个数值 $n$ ，求路径和等于 $n$ 的所有之字形路径的个数。

路径定义:从任意节点到叶子节点的所有节点序列

之字形路径:从任意节点出发，路径中的所有节点需满足如下条件，父节点->左子节点->右子节点->左子节点….…,或者是 父节点->右子节点->左子节点->右子节点->……，之字形路径要求三个节点起。

输入描述

第一行，树的节点个数，$0<$ 节点数 $<=1024$

第二行，数组 $value,value[i]$ 表示第 $i$ 个节点的值，$value>=0$。其中 $-1$ 表示该节点不存在

第三行，目标路径之和 $n,n$ 为 $[0,10000]$

二叉树创建规则:从上到下一层一层，按照从左到右的顺序进行构造

输出描述

输出符合路径和为 $n$ 的之字形路径的个数，若不存在则返回 $-1$ 。

样例1

输入

10
3 2 1 2 1 4 1 -1 -1 5
8

输出

2

说明

有两条路径和为 $8$ 的之字形路径

样例2

输入

3
2 3 1
4

输出

-1

说明

树只有两层，不满足之字形路径的要求，返回 $-1$