编辑代码

const { sourceMapsEnabled } = require("process");

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const midOrder = (await readline()).split(" ").map(Number);
  const preOrder = (await readline()).split(" ").map(Number);
  const n = midOrder.length;
  // 记录中序遍历中的序列元素所在位置
  const map = new Map();
  midOrder.forEach((val, idx) => {
    map.set(val, map.get(val) ? [...map.get(val), idx] : [idx]);
  });
  class TreeNode {
    constructor(val) {
      this.val = val;
      this.left = null;
      this.right = null;
      this.childSum = 0;
    }
  }
  // 判断两个子树是否相同
  const notEquals = (midL, preL, size) => {
    const arr1 = midOrder.slice(midL, midL + size).sort();
    const arr2 = preOrder.slice(preL, preL + size).sort();
    for (let i = 0; i < size; i++) {
      if (arr1[i] !== arr2[i]) {
        return true;
      }
    }
    return false;
  };
  // 根据中序，前序遍历还原树结构
  const buildTree = (midL, midR, preL, preR) => {
    if (preL > preR) return null;
    const rootVal = preOrder(preL);
    const root = new TreeNode(rootVal);
    const idxs = [...map.get(rootVal)];
    for (const idx of idxs) {
      if (idx < midL || idx > midR) continue;
      // 检查中序和前序的左右子树是否相同
      const leftLen = idx - midL;
      if (notEquals(midL, preL + 1, leftLen)) continue;
      const rightLen = midR - idx;
      if (notEquals(idx + 1, preR - rightLen + 1, rightLen)) continue;
      // 找到正确的根后，创建子树
      root.left = buildTree(midL, idx - 1, preL + 1, preL + leftLen);
      root.right = buildTree(idx + 1, midR, preL + leftLen + 1, preR);
      // break;
      root.childSum =
        (root.left ? root.left.val + root.left.childSum : 0) +
        (root.right ? root.right.val + root.right.childSum : 0);
      break;
    }
    return root;
  };
  const getMidOrder = (root, res) => {
    if (!root) return;
    const left = root.left;
    if (left) getMidOrder(left, res);
    res.push(root.val);
    if (root.right) getMidOrder(left, res);
  };
  const root = buildTree(0, n - 1, 0, n - 1);
  const res = [];
  getMidOrder(root, res);
  console.log(res.join(" "));
})();