P4345.第1题-二叉树最长严格交替路径
题目内容
给定一棵二叉树的根节点 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
说明
编入表示如下树
- 20
- /
- 10
- /
- 21
- \
- 11
- \
- 22
- /
- 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
表示如下树
- 10
- / \
- 5 15
- / \ \
- 3 8 20
- / /
- 7 18
满足条件的最长路径为 10−>5−>8
样例3
输入
8 3
10 5 15
5 3 8
15 -1 20
3 -1 -1
8 7 -1
20 18 -1
7 -1 -1
18 -1 -1
输出
3
说明
8 3 表示树的元素为 8 个，阈值为 K=3
8 3
10 5 15
5 3 8
15 -1 20
3 -1 -1
8 7 -1
20 18 -1
7 -1 -1
18 -1 -1
表示如下树
- 10
- / \
- 5 15
- / \ \
- 3 8 20
- / /
- 7 18
满足条件的最长路径为 10−>5−>8
