荧光森林的共鸣路径

题目分析

给定一棵 $n$ 个节点的二叉树（以层序遍历数组表示，-1 表示空节点），要求计算满足条件的"共鸣路径"数量：

起点任意：路径可以从树中任意存在的节点开始
终点必须是叶子节点（无子节点）
之字形规则：第一步方向任意（左或右），之后每一步必须与上一步方向交替（左→右→左→…或右→左→右→…）
长度至少 3：路径上至少包含 3 个节点
能量和等于 target：路径上所有节点的能量值之和恰好等于目标值

输出满足条件的路径数量。特别地，如果树中根本不存在任何满足长度和之字形规则的路径（不考虑能量和），输出 $-1$ ；否则输出匹配 target 的路径数（可以为 0）。

思路

枚举起点 + DFS

由于 $n \leq 1000$ ，可以枚举每个节点作为起点，分别尝试"先往左"和"先往右"两种起始方向，沿着之字形路径一直走到叶子节点。

层序数组中节点 $i$ 的左孩子为 $2i+1$ ，右孩子为 $2i+2$ 。判断一个节点是否为叶子：其左右孩子要么越界、要么值为 $-1$ 。

DFS 过程中维护当前路径和以及路径长度。当到达叶子节点时，若路径长度 $\geq 3$ ，则记为一条有效共鸣路径；若同时路径和等于 target，则计入答案。

由于之字形约束，从每个起点出发的每条路径是唯一确定的（每步只有一个方向可走），因此每次 DFS 的复杂度为 $O(\log n)$ （树的深度）。总时间复杂度 $O(n \log n)$ 。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

int n, target, ans, totalPaths;
vector<int> val;

bool isLeaf(int i) {
    int l = 2*i+1, r = 2*i+2;
    return !(l < n && val[l] != -1) && !(r < n && val[r] != -1);
}

void dfs(int cur, long long curSum, int nextDir, int depth) {
    if (isLeaf(cur)) {
        if (depth >= 3) {
            totalPaths++;
            if (curSum == target) ans++;
        }
        return;
    }
    if (nextDir == 0) {
        int l = 2*cur+1;
        if (l < n && val[l] != -1) dfs(l, curSum + val[l], 1, depth+1);
    } else {
        int r = 2*cur+2;
        if (r < n && val[r] != -1) dfs(r, curSum + val[r], 0, depth+1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    val.resize(n);
    for (int i = 0; i < n; i++) cin >> val[i];
    cin >> target;
    ans = totalPaths = 0;
    for (int i = 0; i < n; i++) {
        if (val[i] == -1) continue;
        dfs(i, val[i], 0, 1);
        dfs(i, val[i], 1, 1);
    }
    cout << (totalPaths == 0 ? -1 : ans) << endl;
    return 0;
}

import java.util.*;

public class Main {
    static int n, target, ans, totalPaths;
    static int[] val;

    static boolean isLeaf(int i) {
        int l = 2*i+1, r = 2*i+2;
        return !(l < n && val[l] != -1) && !(r < n && val[r] != -1);
    }

    static void dfs(int cur, long curSum, int nextDir, int depth) {
        if (isLeaf(cur)) {
            if (depth >= 3) {
                totalPaths++;
                if (curSum == target) ans++;
            }
            return;
        }
        if (nextDir == 0) {
            int l = 2*cur+1;
            if (l < n && val[l] != -1) dfs(l, curSum + val[l], 1, depth+1);
        } else {
            int r = 2*cur+2;
            if (r < n && val[r] != -1) dfs(r, curSum + val[r], 0, depth+1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        val = new int[n];
        for (int i = 0; i < n; i++) val[i] = sc.nextInt();
        target = sc.nextInt();
        ans = totalPaths = 0;
        for (int i = 0; i < n; i++) {
            if (val[i] == -1) continue;
            dfs(i, val[i], 0, 1);
            dfs(i, val[i], 1, 1);
        }
        System.out.println(totalPaths == 0 ? -1 : ans);
    }
}

import sys
sys.setrecursionlimit(100000)

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    n = int(input_data[idx]); idx += 1
    val = [int(input_data[idx+i]) for i in range(n)]; idx += n
    target = int(input_data[idx])

    ans = 0
    total_paths = 0

    def is_leaf(i):
        l, r = 2*i+1, 2*i+2
        return not (l < n and val[l] != -1) and not (r < n and val[r] != -1)

    def dfs(cur, cur_sum, next_dir, depth):
        nonlocal ans, total_paths
        if is_leaf(cur):
            if depth >= 3:
                total_paths += 1
                if cur_sum == target:
                    ans += 1
            return
        if next_dir == 0:
            l = 2*cur+1
            if l < n and val[l] != -1:
                dfs(l, cur_sum + val[l], 1, depth+1)
        else:
            r = 2*cur+2
            if r < n and val[r] != -1:
                dfs(r, cur_sum + val[r], 0, depth+1)

    for i in range(n):
        if val[i] == -1:
            continue
        dfs(i, val[i], 0, 1)
        dfs(i, val[i], 1, 1)

    print(-1 if total_paths == 0 else ans)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const val = lines[1].split(/\s+/).map(Number);
    const target = parseInt(lines[2]);

    let ans = 0, totalPaths = 0;

    function isLeaf(i) {
        const l = 2*i+1, r = 2*i+2;
        return !(l < n && val[l] !== -1) && !(r < n && val[r] !== -1);
    }

    function dfs(cur, curSum, nextDir, depth) {
        if (isLeaf(cur)) {
            if (depth >= 3) {
                totalPaths++;
                if (curSum === target) ans++;
            }
            return;
        }
        if (nextDir === 0) {
            const l = 2*cur+1;
            if (l < n && val[l] !== -1) dfs(l, curSum + val[l], 1, depth+1);
        } else {
            const r = 2*cur+2;
            if (r < n && val[r] !== -1) dfs(r, curSum + val[r], 0, depth+1);
        }
    }

    for (let i = 0; i < n; i++) {
        if (val[i] === -1) continue;
        dfs(i, val[i], 0, 1);
        dfs(i, val[i], 1, 1);
    }

    console.log(totalPaths === 0 ? -1 : ans);
});

复杂度分析

时间复杂度： $O(n \log n)$ 。枚举 $n$ 个起点，每个起点沿之字形路径最多走 $O(\log n)$ 步（树的深度）。
空间复杂度： $O(n)$ 。存储节点数组，递归栈深度为 $O(\log n)$ 。