首页 > 代码库 > 寂寞的堆

寂寞的堆

【题目描述】

我们称满足下列两个条件的满二叉树为寂寞的堆。

(1)对于堆中任意一个儿子节点,其Key值都不大于父亲节点的Key值;

(2)对于堆中任意一个非叶子节点,其左子树中任意节点的Key值都不能大于其右子树任意节点的Key值;

现给定你一棵满二叉树,询问最少修改多少个节点的Key值,才能使它变成寂寞的堆。

【输入描述】

输入第一行是一个数n,表示树共n层;

后面n行,每一行表示该层所有叶子节点的值;

【输出描述】

输出一个数,表示最少修改的节点数。

【样例输入】

2

2

1 2

【样例输出】

0

【数据范围及提示】

对于30%的数据,n <= 2;

对于60%的数据,n <= 10;

对于100%的数据,n <= 18。

寂寞的堆