二叉树4种遍历的基本功 (preOrder, inOrder, postOrder, levelOrder)

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

using namespace std;

int n;

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

// debug helper function
void preOrder(TreeNode* root) {
  if (!root) return;
  printf("%d ", root->val);
  preOrder(root->left);
  preOrder(root->right);
}

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
  unordered_map<int, int> index;
  for (int i = 0; i < inorder.size(); ++i)
    index[inorder[i]] = i;

  function<TreeNode*(int, int, int)> construct = [&](int i, int j, int n) {
    if (n <= 0) return (TreeNode*) nullptr;
    auto root = new TreeNode(postorder[j + n - 1]);
    if (n == 1) return root; // leaf node (without children)

    int k = index[postorder[j + n - 1]]; // O(1)
    int l = k - i; // length of the left subtree

    root->left  = construct(i, j, l);
    root->right = construct(k + 1, j + l, n - 1 - l);

    return root;
  };

  return construct(0, 0, postorder.size());
}

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
  // coner case
  if (!root) return {};

  queue<TreeNode*> q{{root}};

  vector<vector<int>> ans;
  while (not q.empty()) {
    ans.emplace_back();
    size_t sz = q.size();
    while (sz--) {
      auto cur = q.front(); q.pop();
      if (!(ans.size() & 1))  ans.back().emplace_back(cur->val);
      else ans.back().insert(begin(ans.back()), cur->val);

      if (cur->left)  q.emplace(cur->left);
      if (cur->right) q.emplace(cur->right);
    }
  }

  return ans;
}

int main(void) {
  scanf("%d", &n);
  vector<int> inorder(n), postorder(n);
  for (int i = 0; i < n; ++i) cin >> inorder[i];
  for (int i = 0; i < n; ++i) cin >> postorder[i];

  auto ans = zigzagLevelOrder(buildTree(inorder, postorder));
  for (const auto& row : ans)
    for (const auto& x : row) printf("%d ", x);

  return 0;
}