二叉树递归建树与遍历

#include <iostream>
#include <vector>
#include <queue>
#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() {};
};

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

  function<TreeNode*(int, int, int)> build = [&](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;

    // int k = i;
    // while (inorder[k] != postorder[j + n - 1]) ++k;
    int k = indices[postorder[j + n - 1]];
    int l = k - i;

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

    return root;
  };

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

void levelOrder(TreeNode* root) {
  queue<TreeNode*> q{{root}};
  while (not q.empty()) {
    const auto cur = q.front(); q.pop();
    printf("%d ", cur->val);
    if (cur->left)  q.emplace(cur->left);
    if (cur->right) q.emplace(cur->right);
  }
}

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

  levelOrder(buildTree(inorder, postorder));
}