解题思路

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

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

• 做法：

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

• 相关算法：二叉树构造（层序）、DFS（沿固定方向交替向下）。

核心实现要点

• 从某起点出发后，路径方向被完全确定（例如“左→右→左→…”），因此递归/迭代时每层最多继续到一个子节点，复杂度可控。
• 统计总条数，若为 0 输出 -1。

复杂度分析

• 设节点数为 N，树高为 H。从每个节点最多沿两条交替路径向下，各自长度不超过 H， 时间复杂度 O(N * H)（平衡树近似 O(N log N)，退化链表 O(N^2)，题目上限 1024 可接受）。
• 额外空间为递归深度 O(H) 与构造时队列 O(W)（W 为某层宽度），总体 O(H) ~ O(N)。

代码实现

Python

# -*- coding: utf-8 -*-
# ACM 风格：主函数处理输入输出，功能写在外部函数中

import sys
from collections import deque

class Node:
    def __init__(self, v):
        self.v = v
        self.l = None
        self.r = None

def build_tree(arr):
    """按层序数组构造二叉树，-1 表示空"""
    if not arr or arr[0] == -1:
        return None
    root = Node(arr[0])
    q = deque([root])
    i = 1
    n = len(arr)
    while q and i < n:
        cur = q.popleft()
        # 左孩子
        if i < n:
            val = arr[i]; i += 1
            if val != -1:
                cur.l = Node(val)
                q.append(cur.l)
        # 右孩子
        if i < n:
            val = arr[i]; i += 1
            if val != -1:
                cur.r = Node(val)
                q.append(cur.r)
    return root

def count_zigzag_sum(root, target):
    """统计路径和为 target 的之字形路径条数；为 0 返回 -1"""

    def go(node, expect_left, acc, length):
        """
        已经从起点走到 node，下一步期望方向为 expect_left。
        acc 为已累加的和（不含 node 之前已更新），length 为已走节点数。
        只在到达叶子且 length>=3 时计数。
        """
        if node is None:
            return 0
        acc += node.v
        length += 1
        if node.l is None and node.r is None:
            return 1 if (length >= 3 and acc == target) else 0
        if expect_left:
            return go(node.l, False, acc, length) if node.l else 0
        else:
            return go(node.r, True, acc, length) if node.r else 0

    def dfs_all(node):
        nonlocal ans
        if node is None:
            return
        # 两种首步方向
        if node.l:
            ans += go(node.l, False, node.v, 1)
        if node.r:
            ans += go(node.r, True, node.v, 1)
        dfs_all(node.l)
        dfs_all(node.r)

    ans = 0
    dfs_all(root)
    return ans if ans > 0 else -1

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    n = int(data[0])
    arr = list(map(int, data[1:1 + n]))
    target = int(data[1 + n])
    root = build_tree(arr)
    print(count_zigzag_sum(root, target))

if __name__ == "__main__":
    main()

Java

// ACM 风格：主类 Main，主函数读写，功能在静态方法中
import java.util.*;

public class Main {

    // 二叉树节点
    static class Node {
        int v;
        Node l, r;
        Node(int v) { this.v = v; }
    }

    // 按层序数组构造二叉树，-1 表示空
    static Node buildTree(int[] a) {
        if (a.length == 0 || a[0] == -1) return null;
        Node root = new Node(a[0]);
        Queue<Node> q = new ArrayDeque<>();
        q.offer(root);
        int i = 1;
        while (!q.isEmpty() && i < a.length) {
            Node cur = q.poll();
            // 左孩子
            if (i < a.length) {
                int v = a[i++];
                if (v != -1) {
                    cur.l = new Node(v);
                    q.offer(cur.l);
                }
            }
            // 右孩子
            if (i < a.length) {
                int v = a[i++];
                if (v != -1) {
                    cur.r = new Node(v);
                    q.offer(cur.r);
                }
            }
        }
        return root;
    }

    // 统计之字形路径和为 target 的条数；0 条返回 -1
    static int countZigzagSum(Node root, int target) {
        final int[] ans = new int[1];

        // 继续沿指定交替方向向下
        class Helper {
            int go(Node node, boolean expectLeft, int acc, int len) {
                if (node == null) return 0;
                acc += node.v;
                len += 1;
                if (node.l == null && node.r == null) {
                    return (len >= 3 && acc == target) ? 1 : 0;
                }
                if (expectLeft) {
                    return (node.l != null) ? go(node.l, false, acc, len) : 0;
                } else {
                    return (node.r != null) ? go(node.r, true, acc, len) : 0;
                }
            }
        }
        Helper helper = new Helper();

        // 枚举所有起点
        Deque<Node> stack = new ArrayDeque<>();
        if (root != null) stack.push(root);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            if (cur.l != null) ans[0] += helper.go(cur.l, false, cur.v, 1);
            if (cur.r != null) ans[0] += helper.go(cur.r, true, cur.v, 1);
            if (cur.l != null) stack.push(cur.l);
            if (cur.r != null) stack.push(cur.r);
        }
        return ans[0] > 0 ? ans[0] : -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 数据规模小，直接用 Scanner
        if (!sc.hasNextInt()) return;
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();
        int target = sc.nextInt();
        Node root = buildTree(arr);
        int ans = countZigzagSum(root, target);
        System.out.println(ans);
        sc.close();
    }
}

C++

// ACM 风格：主函数处理输入输出，功能在外部函数
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int v;
    Node *l, *r;
    Node(int _v) : v(_v), l(nullptr), r(nullptr) {}
};

// 按层序数组构造二叉树，-1 表示空
Node* buildTree(const vector<int>& a) {
    if (a.empty() || a[0] == -1) return nullptr;
    Node* root = new Node(a[0]);
    queue<Node*> q;
    q.push(root);
    int i = 1, n = (int)a.size();
    while (!q.empty() && i < n) {
        Node* cur = q.front(); q.pop();
        // 左
        if (i < n) {
            int v = a[i++];
            if (v != -1) {
                cur->l = new Node(v);
                q.push(cur->l);
            }
        }
        // 右
        if (i < n) {
            int v = a[i++];
            if (v != -1) {
                cur->r = new Node(v);
                q.push(cur->r);
            }
        }
    }
    return root;
}

// 继续沿交替方向向下
int go(Node* node, bool expectLeft, int acc, int len, int target) {
    if (!node) return 0;
    acc += node->v;
    len += 1;
    if (!node->l && !node->r) {
        return (len >= 3 && acc == target) ? 1 : 0;
    }
    if (expectLeft) {
        return node->l ? go(node->l, false, acc, len, target) : 0;
    } else {
        return node->r ? go(node->r, true, acc, len, target) : 0;
    }
}

// 统计所有起点
int countZigzagSum(Node* root, int target) {
    if (!root) return -1;
    int ans = 0;
    stack<Node*> st;
    st.push(root);
    while (!st.empty()) {
        Node* cur = st.top(); st.pop();
        if (cur->l) ans += go(cur->l, false, cur->v, 1, target);
        if (cur->r) ans += go(cur->r, true,  cur->v, 1, target);
        if (cur->l) st.push(cur->l);
        if (cur->r) st.push(cur->r);
    }
    return ans > 0 ? ans : -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int target; cin >> target;
    Node* root = buildTree(a);
    cout << countZigzagSum(root, target) << "\n";
    return 0;
}

题目内容

给定一个二叉树根节点 $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$