摘要：推導前序序列已知二叉樹的中序序列是，后序序列是，求前序序列。二叉樹的中序序列是按照左子樹，根，右子樹的順序排列的，根將左子樹的序列和右子樹的序列分割在左右兩邊。

已知二叉樹的中序序列是ABCDEFG，后序序列是BDCAFGE，求前序序列。

二叉樹的后序序列是按照「左子樹」，「右子樹」，「根」的順序排列的，序列中最后一個元素代表該二叉樹的根節點。
二叉樹的前序序列是按照「根」，「左子樹」，「右子樹」的順序排列的，序列中第一個元素代表該二叉樹的根節點。故通過已知的后序序列可以發現根，作為前序序列的第一個元素。
二叉樹的中序序列是按照「左子樹」，「根」，「右子樹」的順序排列的，根將左子樹的序列和右子樹的序列分割在左右兩邊。通過后序序列發現根，找到其在中序序列的位置，從而在中序序列中發現左子樹和右子樹并獲得它們的長度，最后在后序序列中找到對應的左子樹和右子樹的后序序列。
這樣求某二叉樹的前序序列，變成了求該二叉樹左子樹的前序序列和該二叉樹右子樹的前序序列。

一棵樹，先找到其根，將其壓入棧中，再將其分割成左右子樹，按左子樹，右子樹的順序，找子樹的根，將其壓入棧中，直到子樹不可分割，得到整棵樹的前序序列。

/**
 * 返回二叉樹的前序序列
 * @param {array} inOrder 
 * @param {array} postOrder 
 * @returns {array} preOrder
 */
function findPreOrder (inOrder, postOrder) {
  let preOrder = []
  // 保存前序序列
  !function findRoot(inOrder, postOrder) {
    if (inOrder.length <= 1) { 
      // 若序列的長度為0或1，停止遞歸調用
      inOrder[0] && preOrder.push(inOrder[0]) 
      // 若序列長度為1，則它就是該樹的根節點，根入棧
      // 在先序序列中，樹的根排列順序先于子樹的根
      return
    } else {
      const root = postOrder[postOrder.length - 1] 
      // 找到根節點
      preOrder.push(root) 
      // 根入棧
      const index = inOrder.indexOf(root) 
      // 找到根節點在中序序列中的位置
      const newInOrderLeft = inOrder.slice(0, index) 
      // 根據根的位置找出左子樹的中序序列
      const newInOrderRight = inOrder.slice(index + 1) 
      // 根據根的位置找出右子樹的中序序列
      const newPostOrderLeft = postOrder.slice(0, newInOrderLeft.length) 
      // 根據左子樹中序序列的長度找出其后序序列
      const newPostOrderRight = postOrder.slice(newInOrderLeft.length, newInOrderRight.length + newInOrderLeft.length) 
      // 根據右子樹中序序列的長度找出其后序序列
      findRoot(newInOrderLeft, newPostOrderLeft)
      // 找到左子樹的根
      findRoot(newInOrderRight, newPostOrderRight)
      // 找到右子樹的根
      // 在先序序列中，左子樹的根排列順序先于右子樹的根
    }
  }(inOrder, postOrder)
  return preOrder
  // 返回前序序列
}

let preOrder = findPreOrder(Array.from("ABCDEFG"), Array.from("BDCAFGE"))
console.log(preOrder)
// [ "E", "A", "C", "B", "D", "G", "F" ]

非遞歸解法和遞歸解法的思路相同，找到根，壓入棧，分割左右子樹，找到它們的根，壓入棧。
不同之處在于用inOrderArr保存待分割的樹的中序序列，用postOrderArr保存待分割的樹的后序序列。

const findPreOrder = (inOrder, postOrder) => {
  let preOrder = [],
  // 保存前序序列
    inOrderArr = [inOrder],
    // 存儲待分割的樹的中序序列，初始狀態為傳入的樹的中序序列
    postOrderArr = [postOrder]
    // 存儲待分割的樹的后序序列，初始狀態為傳入的樹的后序序列
  while (preOrder.length < inOrder.length) {
    let inOrderEle = inOrderArr.shift(),
    // 取出子樹的中序序列
      postOrderEle = postOrderArr.shift()
      // 取出子樹的后序序列
    if (inOrderEle.length <= 1) {
    // 若取出的序列的長度為0或1，就不再分割
      inOrderEle[0] && preOrder.push(inOrderEle[0])
      // 若取出的序列的長度為1，則為根，入棧
    } else {
      let root = postOrderEle[postOrderEle.length - 1]
      // 找到根
      preOrder.push(root)
      // 根入棧
      // 開始分割左右子樹
      const index = inOrderEle.indexOf(root)
      const newinOrderEle1 = inOrderEle.slice(0, index)
      const newinOrderEle2 = inOrderEle.slice(index + 1)
      inOrderArr = [newinOrderEle1, newinOrderEle2, ...inOrderArr] // 用分割后的左右子樹代替原先的樹
      const newpostOrderEle1 = postOrderEle.slice(0, newinOrderEle1.length)
      const newpostOrderEle2 = postOrderEle.slice(newinOrderEle1.length, newinOrderEle1.length + newinOrderEle2.length)
      postOrderArr = [newpostOrderEle1, newpostOrderEle2, ...postOrderArr] // 用分割后的左右子樹代替原先的樹
    }
  }
  return preOrder
  // 返回前序序列
}

let preOrder = findPreOrder(Array.from("ABCDEFG"), Array.from("BDCAFGE"))
console.log(preOrder)
// [ "E", "A", "C", "B", "D", "G", "F" ]

已知二叉樹的前序序列是EACBDGF，中序序列是ABCDEFG，求后序序列。

通過前序序列找到根，找到根在中序序列的位置，將樹分割成左右子樹，按照先右子樹再左子樹的順序找到子樹的根，直至子樹不可分割。先找到的根排在后找到的根的后面。
和推導前序序列，相比思路大致相同，實現細節上，找樹的根的方式不同，分割子樹的方式不同，保存根的方式不同。

const findPostOrder = (preOrder, inOrder) => {
  let postOrder = []
  // 保存后序序列
  !function findRoot(preOrder, inOrder) {
    if(inOrder.length <= 1){
    // 若序列的長度為0或1，停止遞歸調用
      inOrder[0] && postOrder.unshift(inOrder[0])
      // 若序列長度為1，則它就是該樹的根節點，根入棧
      // 在后序序列中，樹的根排列順序后于子樹的根
      return
    }else{
      const root = preOrder[0]
      // 找到根節點
      postOrder.unshift(root)
      // 保存根
      const index = inOrder.indexOf(root)
      // 找到根節點在中序序列中的位置
      const newInOrderLeft = inOrder.slice(0, index)
      // 根據根的位置找出左子樹的中序序列
      const newInOrderRight = inOrder.slice(index + 1)
      // 根據根的位置找出右子樹的中序序列
      const newPreOrderLeft = preOrder.slice(1, newInOrderLeft.length + 1)
      // 根據左子樹中序序列的長度找出其前序序列
      const newPreOrderRight = preOrder.slice(newInOrderLeft.length + 1)
      // 根據右子樹中序序列的長度找出其前序序列
      findRoot(newPreOrderRight, newInOrderRight)
      // 找到右子樹的根
      findRoot(newPreOrderLeft, newInOrderLeft)
      // 找到左子樹的根
    }
  }(preOrder, inOrder)
  return postOrder
  // 返回后序序列
}

let postOrder = findPostOrder(Array.from("EACBDGF"), Array.from("ABCDEFG"))
console.log(postOrder)
// [ "B", "D", "C", "A", "F", "G", "E" ]

非遞歸解法和遞歸解法的思路相同，找到根并保存，分割左右子樹，找到它們的根并保存。
不同之處在于用preOrderArr保存待分割的樹的前序序列，用inOrderArr保存待分割的樹的中序序列，且每次取最后一個元素開始處理。

const findPostOrder = (preOrder, inOrder) => {
  let postOrder = [],
    preOrderArr = [preOrder],
    inOrderArr = [inOrder]
  while (postOrder.length < inOrder.length) {
    let inOrderEle = inOrderArr.pop(),
      preOrderEle = preOrderArr.pop()
    if (inOrderEle.length <= 1) {
      inOrderEle[0] && postOrder.unshift(inOrderEle[0])
    } else {
      let root = preOrderEle[0]
      postOrder.unshift(root)
      const index = inOrderEle.indexOf(root)
      const newinOrderEle1 = inOrderEle.slice(0, index)
      const newinOrderEle2 = inOrderEle.slice(index + 1)
      inOrderArr = [...inOrderArr, newinOrderEle1, newinOrderEle2]
      const newpreOrderEle1 = preOrderEle.slice(1, newinOrderEle1.length + 1)
      const newpreOrderEle2 = preOrderEle.slice(newinOrderEle1.length + 1)
      preOrderArr = [...preOrderArr, newpreOrderEle1, newpreOrderEle2]
    }
  }
  return postOrder
}

console.log(findPostOrder(Array.from("EACBDGF"), Array.from("ABCDEFG")))
// [ "B", "D", "C", "A", "F", "G", "E" ]

那是不可能的！

已知前序序列ABC，后序序列CBA，求中序序列。

這是一道多解題。

推薦結合nodemon在node環境下學習算法。