解题思路

• 定义与要求 路径只能自上而下（父 → 子）；相邻节点的值必须严格交替增减，且每一步的绝对差值 ≥ k。路径长度为路径中的节点数。

• 算法：树形 DP（自顶向下或后序） 对每个结点 u 维护两种状态：

  • up[u]：从 u 出发，第一步向更大值的孩子走的最长交替路径长度。
  • down[u]：从 u 出发，第一步向更小值的孩子走的最长交替路径长度。 转移（左右孩子分别为 v）：

  若 v!=-1 且 val[v] - val[u] >= k:  up[u]   = max(up[u],   1 + down[v])
  若 v!=-1 且 val[u] - val[v] >= k:  down[u] = max(down[u], 1 + up[v])
  

  初值均为 1（只取当前结点）。答案为 max_u( max(up[u], down[u]) )。

• 实现要点

  • 用字典/哈希表记录每个值对应的左右孩子（输入保证值唯一）。
  • Python 用记忆化 DFS；Java/C++ 用显式栈的后序遍历避免深递归风险。
  • 按输入 N K，随后 N 行 X Y Z（缺失孩子为 -1）。

复杂度分析

• 时间复杂度：每条边最多被检查两次，O(N)。
• 空间复杂度：存图与 DP 数组/哈希表，O(N)。

代码实现

Python

# ACM 风格：主函数读写，功能函数在外部；中文注释
import sys

sys.setrecursionlimit(1_000_000)

def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    K = next(it)

    # children[v] = [left, right]，结点用其值标识
    children = {}
    nodes = set()

    for _ in range(N):
        x = next(it); y = next(it); z = next(it)
        children[x] = [y, z]
        nodes.add(x)
        if y != -1: nodes.add(y)
        if z != -1: nodes.add(z)

    memo_up = {}
    memo_down = {}

    # 从u出发，第一步向更大值走
    def up(u):
        if u in memo_up:
            return memo_up[u]
        res = 1  # 仅u本身
        for v in children.get(u, []):
            if v != -1 and v - u >= K:
                res = max(res, 1 + down(v))
        memo_up[u] = res
        return res

    # 从u出发，第一步向更小值走
    def down(u):
        if u in memo_down:
            return memo_down[u]
        res = 1
        for v in children.get(u, []):
            if v != -1 and u - v >= K:
                res = max(res, 1 + up(v))
        memo_down[u] = res
        return res

    ans = 0
    for u in nodes:
        ans = max(ans, up(u), down(u))
    print(ans)

if __name__ == "__main__":
    solve()

Java

// Java：节点值范围 ≤ 1e5，直接用数组，不用 Map；显式栈做后序，避免深递归
import java.io.*;
import java.util.*;

public class Main {
    // 计算最长严格交替路径（相邻差值 ≥ K），从森林任意节点出发向下走
    // L/R：孩子数组；present：该值是否为节点；nodes：出现过的所有节点值
    static int computeAnswer(int K, int[] L, int[] R, boolean[] present, List<Integer> nodes) {
        final int MAXV = L.length - 1;

        // DP：从 u 出发，第一步向更大值走/向更小值走 的最长长度
        int[] up = new int[MAXV + 1];
        int[] down = new int[MAXV + 1];
        boolean[] done = new boolean[MAXV + 1];

        // 初始化 DP 为 1（只取自身）
        for (int u : nodes) {
            up[u] = 1;
            down[u] = 1;
        }

        // 对森林中每个未处理的节点做一次“显式栈后序遍历”
        ArrayDeque<int[]> st = new ArrayDeque<>(); // 元素：{u, backFlag(0/1)}
        for (int s : nodes) {
            if (done[s]) continue;

            st.clear();
            st.push(new int[]{s, 0});
            while (!st.isEmpty()) {
                int[] cur = st.pop();
                int u = cur[0];
                int back = cur[1];

                if (back == 1) {
                    // 处理回溯：根据已知的子节点 DP 更新当前节点
                    int bestUp = 1, bestDown = 1;
                    int[] ch = { L[u], R[u] };
                    for (int v : ch) {
                        if (v == -1) continue;
                        // v 已经在回溯时处理完（或本就是叶子），up[v]/down[v] 已就绪
                        if (v - u >= K) bestUp   = Math.max(bestUp,   1 + down[v]); // 先升：下一步需降
                        if (u - v >= K) bestDown = Math.max(bestDown, 1 + up[v]);   // 先降：下一步需升
                    }
                    up[u] = bestUp;
                    down[u] = bestDown;
                    done[u] = true;
                } else {
                    if (done[u]) continue;
                    // 先压回当前节点（back=1），再压孩子（back=0）
                    st.push(new int[]{u, 1});
                    int lv = L[u], rv = R[u];
                    if (lv != -1 && !done[lv]) st.push(new int[]{lv, 0});
                    if (rv != -1 && !done[rv]) st.push(new int[]{rv, 0});
                }
            }
        }

        // 取全局最大值
        int ans = 0;
        for (int u : nodes) ans = Math.max(ans, Math.max(up[u], down[u]));
        return ans;
    }

    public static void main(String[] args) throws Exception {
        // 读入：N K；随后 N 行 x y z（缺失为 -1）
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        if (line == null || line.trim().isEmpty()) return;
        StringTokenizer st = new StringTokenizer(line);
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        final int MAXV = 100000; // 节点值范围上限
        int[] L = new int[MAXV + 1];
        int[] R = new int[MAXV + 1];
        boolean[] present = new boolean[MAXV + 1];
        Arrays.fill(L, -1);
        Arrays.fill(R, -1);

        List<Integer> nodes = new ArrayList<>(N * 2);

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());

            L[x] = y;
            R[x] = z;

            if (!present[x]) { present[x] = true; nodes.add(x); }
            if (y != -1 && !present[y]) { present[y] = true; nodes.add(y); }
            if (z != -1 && !present[z]) { present[z] = true; nodes.add(z); }
        }

        int ans = computeAnswer(K, L, R, present, nodes);
        System.out.println(ans);
    }
}

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    // children[x] = {left, right}
    unordered_map<int, pair<int,int> > children;
    unordered_set<int> nodes;

    for (int i = 0; i < N; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        children[x] = make_pair(y, z);
        nodes.insert(x);
        if (y != -1) nodes.insert(y);
        if (z != -1) nodes.insert(z);
    }

    // DP 结果：从 u 出发，第一步升/降 的最长长度
    unordered_map<int,int> up, down;
    unordered_set<int> done;

    for (int start : nodes) {
        if (done.count(start)) continue;

        vector<pair<int,bool> > st;           // {node, back}
        st.push_back(make_pair(start, false));
        unordered_set<int> seen; seen.insert(start);

        while (!st.empty()) {
            pair<int,bool> cur = st.back(); st.pop_back();
            int u = cur.first; bool back = cur.second;

            if (back) {
                int bestUp = 1, bestDown = 1;
                pair<int,int> ch = make_pair(-1, -1);
                if (children.count(u)) ch = children[u];

                int vs[2] = { ch.first, ch.second };
                for (int i = 0; i < 2; ++i) {
                    int v = vs[i];
                    if (v == -1) continue;
                    // 确保子节点已经有 DP 值；若没有，按 1 处理（叶子）
                    int upv   = up.count(v)   ? up[v]   : 1;
                    int downv = down.count(v) ? down[v] : 1;

                    if (v - u >= K) bestUp   = max(bestUp,   1 + downv);
                    if (u - v >= K) bestDown = max(bestDown, 1 + upv);
                }
                up[u] = bestUp; down[u] = bestDown;
                done.insert(u);
            } else {
                if (done.count(u)) continue;
                st.push_back(make_pair(u, true));
                pair<int,int> ch = make_pair(-1, -1);
                if (children.count(u)) ch = children[u];
                int vs[2] = { ch.first, ch.second };
                for (int i = 0; i < 2; ++i) {
                    int v = vs[i];
                    if (v != -1 && !done.count(v) && !seen.count(v)) {
                        st.push_back(make_pair(v, false));
                        seen.insert(v);
                    }
                }
            }
        }
    }

    int ans = 0;
    for (int u : nodes) {
        int upu = up.count(u) ? up[u] : 1;
        int downu = down.count(u) ? down[u] : 1;
        ans = max(ans, max(upu, downu));
    }
    cout << ans << "\n";
    return 0;
}

题目内容

给定一棵二叉树的根节点 $root$ 和一个整数 $k$ ，定义一条严格交替路径如下:

路径方向:只能从父节点向子节点方向延伸(即路径必须自上而下)。

严格交替条件:路径中相邻节点的值必须交替递增和递减。例如，路径可以是 $3→7→5→9$ (即 $3<7>5<9)$

差值限制:每一步的绝对差值必须严格大于等于 $k$ 。例如，若 $k=2$ ，则 $3→7$ 是合法的(差值为 $4 >2$ )，但 $3→4$ 不合法(差值为 $1<2$ ，不满足严格大于等于)。

“先减小后增加“和“先增加后减少”都算交替

请编写一个函数，返回这棵二叉树中最长严格交替路径的长度。路径长度定义为路径中节点的数量。

输入描述

第 $1$ 行 $N$ $K$

$N$ 为树的元系数量,$N$ 的范围为 $[1,10000]$

$K$ 为阈值。$K$ 的范围为 $[1,100]$

第 $2$ 到第 $N+1$ 行为按 $X$ $Y$ $Z$ 表示一个二叉树节点和子节点的关系，其中 $X$ 为父节点，$Y$ 为左节点，$Z$ 为右节点，缺失的叶子节点用 $-1$ 表示。树的节点值 $X$ $Y$ $Z$ 的取值范围为 $[1,100000]$，元素的值不重复。从上到下按树的先序遍历方式排列

输出描述

输出 $1$ 个数字，表示最长严格交替路径的长度

样例1

输入

6 10
20 10 -1
10 21 -1
21 -1 11
11 -1 22
22 12 -1
12 -1 -1

输出

6

说明

编入表示如下树

1. ​ 20
2. ​ /
3. ​ 10
4. ​ /
5. ​ 21
6. ​ \
7. ​ 11
8. ​ \
9. ​ 22
10. ​ /
11. ​ 12

满足条件的最长路径为 $20->10->20->10->20->10$ ,长度为 $6$

样例2

输入

15 5
25 12 42
12 5 18
42 37 50
5 3 9
18 15 21
37 30 45
50 49 2
3 -1 -1
9 -1 -1
15 -1 -1
21 -1 -1
30 -1 -1
45 -1 -1
49 -1 -1
2 -1 -1

输出

4

说明

$15$ $10$ 表示树的元素为 $15$ 个，阈值为 $10$

12 5 18
42 37 50
5 3 9
18 15 21
37 30 45
50 49 2
3 -1-1
9 -1 -1
15 -1 -1
21 -1 -1
30 -1 -1
45 -1 -1
49 -1 -1
2 -1 -1

表示如下树

1. ​ 10
2. ​ / \
3. ​ 5 15
4. ​ / \ \
5. ​ 3 8 20
6. ​ / /
7. ​ 7 18

满足条件的最长路径为 $10->5->8$

样例3

输入

8 3
10 5 15
5 3 0
15 -1 20
3 -1 -1
8 7 -1
20 18 -1
7 -1 -1
18 -1 -1

输出

3

说明

$8$ $3$ 表示树的元素为 $8$ 个，阈值为 $K=3$

10 5 15
5 3 0
15 -1 20
3 -1 -1
8 7 -1
20 18 -1
7 -1 -1
18 -1 -1

表示如下树

1. ​ 10
2. ​ / \
3. ​ 5 15
4. ​ / \ \
5. ​ 3 8 20
6. ​ / /
7. ​ 7 18

满足条件的最长路径为 $10->5->8$