Binary Tree Traversal

#include <iostream>
#include <vector>
#include <unordered_map>
#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(int _val, TreeNode* _left, TreeNode* _right) : val(_val), left(_left), right(_right) {};
  ~TreeNode() {};
};

bool flag;

TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
  unordered_map<int, int> indices;
  for (int i = 0; i < post.size(); ++i)
    indices[post[i]] = i;

  function<TreeNode*(int, int, int)> construct = [&](int i, int j, int n) {
    // base case
    if (n <= 0) return (TreeNode*) nullptr;
    auto root = new TreeNode(pre[i]);
    if (n == 1) return root;
    if (n == 2) flag = false;

    int k = indices[pre[i + 1]];
    int l = k - j + 1;

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

    return root;
  };

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

void inOrder(TreeNode* root, vector<int>& ans) {
  if (!root) return;
  inOrder(root->left, ans);
  ans.emplace_back(root->val);
  inOrder(root->right, ans);
}

void printAnswer(vector<int>& ans) {
  for (int i = 0; i < ans.size(); ++i) {
    printf("%d", ans[i]);
    if (i < ans.size() - 1) printf(" ");
  }
  printf("\n");
} 

int main(void) {
  // initialize global variable
  flag = true; // 给定一组前序遍历和后序遍历能否唯一确定一颗树 （default: TRUE）

  cin >> n;
  vector<int> pre(n), post(n);
  for (int i = 0; i < n; ++i) cin >> pre[i];
  for (int i = 0; i < n; ++i) cin >> post[i];
  auto root = constructFromPrePost(pre, post);
  puts(flag ? "Yes" : "No");

  vector<int> ans;
  inOrder(root, ans);
  printAnswer(ans);
}