堆的基本功

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
int n;

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {};
  TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {};
  ~TreeNode() {};
};

TreeNode* buildTree(vector<int>& vals) {
  // corner case
  if (vals.empty()) return nullptr;

  auto root = new TreeNode(vals.front());
  queue<pair<TreeNode*, int>> q;
  q.emplace(root, 0);

  while (not q.empty()) {
    const auto [cur, idx] = q.front(); q.pop();
    const int l_idx = idx << 1 | 1;
    if (l_idx >= n) break;
    cur->left = new TreeNode(vals[l_idx]);
    q.emplace(cur->left, l_idx);

    const int r_idx = (idx << 1) + 2;
    if (r_idx >= n) break;
    cur->right = new TreeNode(vals[r_idx]);
    q.emplace(cur->right, r_idx);
  }

  return root;
}

vector<vector<int>> binaryTreePaths(TreeNode* root) {
  vector<vector<int>> ans;
  vector<int> cur;
  function<void(TreeNode*)> backtracking = [&](TreeNode* r) {
    if (!r) return;
    cur.emplace_back(r->val);
    if (r->left == r->right) {
      ans.emplace_back(cur);
      return;
    }
    for (const auto& child : {r->right, r->left}) {
      if (!child) continue;
      backtracking(child);
      cur.pop_back();
    }
  };

  backtracking(root);
  return ans;
}

void printPaths(vector<vector<int>>& paths) {
  for (const auto& p : paths) {
    for (int i = 0; i < p.size(); ++i) {
      printf("%d", p[i]);
      if (i < p.size() - 1) printf(" ");
    }
    printf("\n");
  }
}

bool is_maximum_heap(vector<vector<int>>& paths) {
  for (const auto& p : paths) 
    if (!is_sorted(rbegin(p), rend(p))) return false;

  return true;
}

bool is_minimum_heap(vector<vector<int>>& paths) {
  for (const auto& p : paths) 
    if (!is_sorted(begin(p), end(p))) return false;

  return true;
}
int main(void) {
  cin >> n;
  vector<int> vals(n);
  for (int i = 0; i < n; ++i) cin >> vals[i];
  auto paths = binaryTreePaths(buildTree(vals));
  printPaths(paths);

  if (is_maximum_heap(paths)) puts("Max Heap");
  else if (is_minimum_heap(paths)) puts("Min Heap");
  else puts("Not Heap");
}