按顺序创建最大树

Question

令A为n个不同整数的数组。让的最大元素的索引甲 BE 米。限定在最大树甲成为上的条目二进制树甲其中根目录中包含的最大元素甲，左子是在最大树甲 [ 0：M-1 ]和右子是A [ m + 1：n-1 ] 上的最大树。设计用于构建最大树的O（n）算法。

如果我创建一个虚拟示例，结果发现给定的数组是max-tree的INORDER遍历，对于子树的根上的给定条件，它们应该是最大的。

Answer 1

确实有可能在O（n）时间内完成。我还附带了一些测试用例，它们将我的解决方案与参考O（n log n）解决方案进行了比较。解决方法：

一些观察：

1. 提供的数组是有问题的树的有序遍历。
2. 树具有最大堆属性，即，节点的祖先值不能小于其自身。

方法：我们将从头到尾遍历输入数组，并维护一个堆栈，其中包含值递减的节点（从下至上）。该堆栈将在顶部包含最近构造的节点，在底部包含最大值（根）的节点。

当我们遍历数组时：

1. 如果堆栈为空，则将此节点推入堆栈。
2. 如果stack不为空，并且包含一些值小于当前值的节点，则这些值中的最大值将是当前节点的左子节点。不断弹出值，直到堆栈为空或堆栈顶部包含一个值>当前值。这来自观察值＃1和＃2。
3. 当前节点可以是堆栈顶部节点的右子节点。我们可以假设这一点，直到看到更大的值为止。

由于每个节点都会被扫描一次并压入堆栈，因此这是O（n）时间的解决方案。

这是代码。main函数创建一个10,000个数字的随机数组，并使用上述O（n）算法和朴素的O（n log n）解构造max-tree。我这样做了1000次，并断言两棵树是相等的。

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits>
#include <cassert>
#include <stack>
#include <limits>

using namespace std;

struct Node {
  int data;
  Node* left, *right;
};

/******************** Solution Begin ***************************/
Node* Construct(const vector<int>& array) {
  stack<Node*> S;

  for (auto&& x : array) {
    Node* node = new Node{x, nullptr, nullptr};

    while (!S.empty() && (S.top()->data < x)) {
      node->left = S.top();
      S.pop();
    }

    if (!S.empty()) {
      S.top()->right = node;
    }
    S.emplace(node);
  }

  Node* last_popped = nullptr;
  while (!S.empty()) {
    last_popped = S.top();
    S.pop();
  }

  return last_popped;
}

/******************** Solution End ***************************/

Node* SlowConstructHelper(const vector<int>& array, int start, int end) {
  if (start > end) return 0;

  int m = start;
  for (int i = start + 1; i <= end; i++) {
    if (array[i] > array[m]) m = i;
  }

  Node* root = new Node;
  root->data = array[m];
  root->left = SlowConstructHelper(array, start, m - 1);
  root->right = SlowConstructHelper(array, m + 1, end);
  return root;
}

Node* SlowConstruct(const vector<int>& array) {
  return SlowConstructHelper(array, 0, array.size() - 1);
}

bool IsEqualTree(Node* tree1, Node* tree2) {
  if ((!tree1) && (!tree2)) return true;

  if ((!tree1) || (!tree2)) return false;

  return (tree1->data == tree2->data) &&
         IsEqualTree(tree1->left, tree2->left) &&
         IsEqualTree(tree1->right, tree2->right);
}

int main() {
  const int kNumRuns = 1000;
  const int kArraySize = 10000;

  for (int run = 0; run < kNumRuns; run++) {
    vector<int> array(kArraySize);
    for (int i = 0; i < kArraySize; i++) array[i] = i;  // Uniqueness guaranteed

    random_shuffle(array.begin(), array.end());

    Node* root1 = Construct(array);
    Node* root2 = SlowConstruct(array);
    assert(IsEqualTree(root1, root2));
  }
  return 0;
}

编辑：早期版本声称该树是最大堆。已将其更正为“最大堆属性”。

Answer 2

理论上，在 O(n) 时间内完成这件事看起来是不可能的，因为到目前为止世界上不存在可以在 O(n) 时间内对条目进行排序的算法。并且任何类型的调整逻辑都可以构建在排序条目上，仅用于构建树。

可以完成更坏情况 O(n2) 的正常递归实现。我在《编程面试要素》一书中看到了同样的问题，但他们没有提供任何解决方案。也可能是打字错误。

递归逻辑。

CreateTree(start, end)
if start > end return null
Find index in array between start and end inclusive which contain max value
Create Node with index value
Node.left = CreateTree(start, index - 1);
Node.right = CreateTree(index + 1, end);