Powered by:NEFU AB-IN

Link

4279. 笛卡尔树

• 题意

  笛卡尔树 是由一系列不同数字构成的二叉树。
  树满足堆的性质，中序遍历返回原始序列。
  最小笛卡尔树表示满足小根堆性质的笛卡尔树。
  例如，给定序列 {8,15,3,4,1,5,12,10,18,6}，则生成的最小堆笛卡尔树如图所示。
  现在，给定一个长度为 N 的原始序列，请你生成最小堆笛卡尔树，并输出其层序遍历序列。

• 思路

  最小笛卡尔树：要求中序遍历为原数组，且满足最小堆的性质

  • 所以找到数组的最小值作为根节点，左边的节点都在根节点的左子树上，右边的节点都在根节点的右子树上，递归这个过程即可构建笛卡尔树。
  • 层次遍历也很容易实现，笛卡尔树本身就是从上到下，从左到右构建的，在构建过程中进行节点记录即可完成层次遍历输出。
  • ps: 当然也可以单调栈线性建树

• 代码

  /* * @Author: NEFU AB-IN * @Date: 2022-07-23 14:09:15 * @FilePath: \Acwing\4279\4279.cpp * @LastEditTime: 2022-07-23 14:59:03 */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define IOS \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0);
  #define DEBUG(X) cout << #X << ": " << X << endl;
  typedef pair<int, int> PII;
  
  const int INF = INT_MAX;
  const int N = 1e6 + 10;
  
  signed main()
  {
        
      IOS;
      int n;
      cin >> n;
      vector<int> a(n), L(n), R(n);
      for (int i = 0; i < n; ++i)
      {
        
          cin >> a[i];
      }
      
      // 正常DFS建树
      function<int(int, int)> dfs = [&](int l, int r) {
        
          if (l > r)
              return -1LL;
          int root = min_element(a.begin() + l, a.begin() + r + 1) - a.begin();
          L[root] = dfs(l, root - 1);
          R[root] = dfs(root + 1, r);
          return root;
      };
  
      int root = dfs(0, n - 1);
  
      queue<int> q;
      q.push(root);
      while (SZ(q))
      {
        
          auto t = q.front();
          q.pop();
          cout << a[t] << " ";
          if (L[t] != -1)
              q.push(L[t]);
          if (R[t] != -1)
              q.push(R[t]);
      }
      return 0;
  }