从前序遍历构建笛卡尔树

什么是笛卡尔树？

笛卡尔树是一种从数据集中创建的树形数据结构。笛卡尔树必须遵循以下一些结构变体。

1. 笛卡尔树必须遵守最小堆或最大堆属性。此属性表明每个节点必须小于或大于其子节点。
2. 每个节点的值必须按照初始序列的特定顺序排列。

现在，我们将根据给定的笛卡尔树（按先序遍历排序）创建一个完整的树。

让我们通过一个例子来理解这一点。

输入： arr[] = {1, 5, 3}

输出 1 5 3

  5
 / \
1   3

输入： arr[] = {3, 7, 4, 8}

输出 3 7 4 8

     8
    /
   7
  / \
 3   4

方法

我们知道这种方法的平均时间复杂度为 O(NlogN)，最坏情况下的时间复杂度为 O(N2)。

算法

要解决这个问题，我们必须遵循以下步骤。这些步骤如下：

1. 首先，我们必须找到范围 L 到 R 之间的最大元素。我们可以借助线段树上的范围最大查询找到它。假设 M 是范围 L 到 R 之间最大元素的索引。
2. 然后，我们必须找到 arr[M]，然后我们通过取这个值来创建根节点。
3. 然后，我们必须分别解决范围 {L, M-1} 和 {M+1, R}。
4. 然后，我们必须以这样一种方式设置节点，使其将 {L, M-1} 作为当前节点的左子节点，将 {M+1, R} 作为右子节点。

让我们借助一种编程语言来实现这个算法。

C++ 中的实现

代码

输出

说明

在上面的代码中，我们实现了创建给定笛卡尔树结构的代码。我们使用 C++ 编程语言编写了逻辑。

时间复杂度

此方法的 time complexity 为 O(N+logN)。

空间复杂度

此方法的 space complexity 为 O(N)。