在提瓦特大陆的某个神秘区域,存在一种特殊的树状结构,被称为 “骗骗花结构”(某个打胡桃天赋材料的人悟到的),它用来模拟骗骗花之间的元素关联情况。我们使用数组来模拟这个结构,假设每个 “骗骗花结构” 最多有 100 个节点(仅为示例方便设定节点数量上限,可按需调整),定义结构体如下:
#define MAX_NODES 100
typedef struct {
int elementPower[MAX_NODES]; // 骗骗花蕴含的元素之力数值,下标对应节点顺序
int leftChild[MAX_NODES]; // 记录每个节点左子节点的下标,-1 表示无左子节点
int rightChild[MAX_NODES]; // 记录每个节点右子节点的下标,-1 表示无右子节点
} HilichurlTrickFlower;
“复杂稳定骗骗花形态” 定义
一个 “骗骗花结构” 被称为 “复杂稳定骗骗花形态”,需满足以下条件:
- 对于任意节点,其左右子树所蕴含的元素之力总和的差值的绝对值不超过该节点自身元素之力数值的一半(向下取整)。
- 每个节点的元素之力数值范围是 1 到 100 之间的整数。
- 树的高度(从根节点到最远叶子节点的最长路径上的节点数)不超过 10。
请你编写一个函数,接收一个 “骗骗花结构” 变量,判断该结构是否为 “复杂稳定骗骗花形态”,并在主函数中进行输入输出的处理。
数据范围
- 节点数量 :
- 每个节点元素之力数值:
elementPower[i]
,其中 为节点下标 - 树的高度:不超过 10
样例 1:
- 输入:
5
3 2 4 1 5
1 3 -1 -1 -1
2 4 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
- 输出:
YES
解释:
根节点元素之力为 3,左子树元素之力总和为 2,右子树元素之力总和为 4,差值绝对值为 2,不超过根节点元素之力 3 的一半(向下取整为 1)。其他节点同理,且树高为 3,满足 “复杂稳定骗骗花形态” 的所有条件。