A51462. （笛卡尔树 ）对于一个给定的两两不等的正整数序列， 笛卡尔树是这样的一棵二叉树。首先，它是一个最小堆，即 除了根结点外， 每个结点的权值都大于父结点的权值； 其次， 它的中序遍历恰好就是给定的序列。例如，对于序列 7、2 、12 、1、10 、5、15 、3 ，下图就是一棵对应的笛卡尔树。 现输入序列的规模 n（1<=n<100 ） 和序列的 n 个元素，试求对应的笛卡尔树的深度 d（根节点深度…
填空题
较易
知识点
题目描述
（笛卡尔树 ）对于一个给定的两两不等的正整数序列， 笛卡尔树是这样的一棵二叉树。首先，它是一个最小堆，即 除了根结点外， 每个结点的权值都大于父结点的权值； 其次， 它的中序遍历恰好就是给定的序列。例如，对于序列 7、2 、12 、1、10 、5、15 、3 ，下图就是一棵对应的笛卡尔树。 现输入序列的规模 n（1<=n<100 ） 和序列的 n 个元素，试求对应的笛卡尔树的深度 d（根节点深度为 1），以及有多少个叶节 点的深度为 d 。
【程序清单】
参考答案
<p>1.num++</p><p><br/></p><p>2.j = i</p><p><br/></p><p>3.solve(left, j – 1, deep + 1)</p><p><br/></p><p>4.solve(j + 1, right, deep + 1)</p>
上一题
下一题