山峰间的极限跳跃

题目分析

给定一棵 个节点的二叉树（以先序遍历方式输入），每个节点有一个海拔值。要求找到最长的「极限交替路径」，路径规则为：

  1. 方向约束：只能从父节点走向子节点（严格向下）
  2. 交替约束：相邻两步的海拔变化方向必须交替（升→降→升→…或降→升→降→…）
  3. 阈值约束：每一步的海拔差绝对值不小于

输出路径上的最大节点数。

思路

建树 + 枚举起点 DFS

首先根据先序遍历输入建树。输入的每一行包含当前节点的海拔值以及左右孩子的海拔值（-1 表示无孩子）。按先序遍历顺序，依次分配节点编号并递归构建左子树和右子树。

建树完成后，枚举每个节点作为路径的起点，向下做 DFS，维护当前路径长度和上一步的方向（升或降）。对于每个孩子节点，检查：

  • 海拔差绝对值是否
  • 方向是否与上一步交替（起点的第一步无方向约束）

取所有路径中的最大长度即为答案。

，树的深度最多 ，枚举起点 ，每次 DFS 最多访问子树中所有节点，总时间复杂度 ，完全可行。

代码

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

int n, k;
struct Line { int val, l, r; };
vector<Line> lines;
struct Node { int val, left, right; };
vector<Node> tree;
int idx;

void buildTree(int cur) {
    tree[cur].val = lines[cur].val;
    tree[cur].left = tree[cur].right = -1;
    if (lines[cur].l != -1) { idx++; tree[cur].left = idx; buildTree(idx); }
    if (lines[cur].r != -1) { idx++; tree[cur].right = idx; buildTree(idx); }
}

int dfs(int u, int dir) {
    int best = 0;
    int children[2] = {tree[u].left, tree[u].right};
    for (int c : children) {
        if (c == -1) continue;
        int diff = tree[c].val - tree[u].val;
        if (abs(diff) < k) continue;
        int nd = diff > 0 ? 1 : -1;
        if (dir == 0 || nd != dir) best = max(best, 1 + dfs(c, nd));
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    lines.resize(n); tree.resize(n);
    for (int i = 0; i < n; i++) cin >> lines[i].val >> lines[i].l >> lines[i].r;
    idx = 0; buildTree(0);
    int ans = 1;
    for (int i = 0; i < n; i++) ans = max(ans, 1 + dfs(i, 0));
    cout << ans << endl;
}

import java.util.*;

public class Main {
    static int[] val, left, right;
    static int idx, n, k;

    static void buildTree(int cur, int[][] lines) {
        val[cur] = lines[cur][0];
        left[cur] = right[cur] = -1;
        if (lines[cur][1] != -1) { idx++; left[cur] = idx; buildTree(idx, lines); }
        if (lines[cur][2] != -1) { idx++; right[cur] = idx; buildTree(idx, lines); }
    }

    static int dfs(int u, int dir) {
        int best = 0;
        int[] children = {left[u], right[u]};
        for (int c : children) {
            if (c == -1) continue;
            int diff = val[c] - val[u];
            if (Math.abs(diff) < k) continue;
            int nd = diff > 0 ? 1 : -1;
            if (dir == 0 || nd != dir) best = Math.max(best, 1 + dfs(c, nd));
        }
        return best;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); k = sc.nextInt();
        int[][] lines = new int[n][3];
        val = new int[n]; left = new int[n]; right = new int[n];
        for (int i = 0; i < n; i++) {
            lines[i][0] = sc.nextInt();
            lines[i][1] = sc.nextInt();
            lines[i][2] = sc.nextInt();
        }
        idx = 0; buildTree(0, lines);
        int ans = 1;
        for (int i = 0; i < n; i++) ans = Math.max(ans, 1 + dfs(i, 0));
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    data = []
    for _ in range(n):
        v, l, r = map(int, input().split())
        data.append((v, l, r))

    val = [0] * n
    left = [-1] * n
    right = [-1] * n

    # 迭代先序建树
    idx = 0
    stack = [(0, 0)]
    val[0] = data[0][0]
    while stack:
        cur, phase = stack.pop()
        if phase == 0:
            stack.append((cur, 1))
            if data[cur][1] != -1:
                idx += 1
                left[cur] = idx
                val[idx] = data[idx][0]
                stack.append((idx, 0))
        else:
            if data[cur][2] != -1:
                idx += 1
                right[cur] = idx
                val[idx] = data[idx][0]
                stack.append((idx, 0))

    # 枚举起点，迭代 DFS
    ans = 1
    for start in range(n):
        st = [(start, 0, 1)]
        while st:
            u, d, length = st.pop()
            if length > ans:
                ans = length
            for c in (left[u], right[u]):
                if c == -1:
                    continue
                diff = val[c] - val[u]
                if abs(diff) < k:
                    continue
                nd = 1 if diff > 0 else -1
                if d == 0 or nd != d:
                    st.append((c, nd, length + 1))
    print(ans)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l.trim()));
rl.on('close', () => {
    const [n, k] = lines[0].split(' ').map(Number);
    const data = [];
    for (let i = 1; i <= n; i++) {
        const [v, l, r] = lines[i].split(' ').map(Number);
        data.push([v, l, r]);
    }
    const val = new Array(n), left = new Array(n).fill(-1), right = new Array(n).fill(-1);
    let idx = 0;
    function build(cur) {
        val[cur] = data[cur][0];
        if (data[cur][1] !== -1) { idx++; left[cur] = idx; build(idx); }
        if (data[cur][2] !== -1) { idx++; right[cur] = idx; build(idx); }
    }
    build(0);

    function dfs(u, dir) {
        let best = 0;
        for (const c of [left[u], right[u]]) {
            if (c === -1) continue;
            const diff = val[c] - val[u];
            if (Math.abs(diff) < k) continue;
            const nd = diff > 0 ? 1 : -1;
            if (dir === 0 || nd !== dir) best = Math.max(best, 1 + dfs(c, nd));
        }
        return best;
    }

    let ans = 1;
    for (let i = 0; i < n; i++) ans = Math.max(ans, 1 + dfs(i, 0));
    console.log(ans);
});

复杂度分析

  • 时间复杂度：。枚举 个起点，每次 DFS 最多遍历子树全部节点。
  • 空间复杂度：。存储树结构和 DFS 栈空间。