解题思路

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

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

  • up[u]：从 u 出发，第一步向更大值的孩子走的最长交替路径长度。
  • down[u]：从 u 出发，第一步向更小值的孩子走的最长交替路径长度。

题目内容

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