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

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

二叉樹(shù)的后序序列是按照「左子樹(shù)」，「右子樹(shù)」，「根」的順序排列的，序列中最后一個(gè)元素代表該二叉樹(shù)的根節(jié)點(diǎn)。
二叉樹(shù)的前序序列是按照「根」，「左子樹(shù)」，「右子樹(shù)」的順序排列的，序列中第一個(gè)元素代表該二叉樹(shù)的根節(jié)點(diǎn)。故通過(guò)已知的后序序列可以發(fā)現(xiàn)根，作為前序序列的第一個(gè)元素。
二叉樹(shù)的中序序列是按照「左子樹(shù)」，「根」，「右子樹(shù)」的順序排列的，根將左子樹(shù)的序列和右子樹(shù)的序列分割在左右兩邊。通過(guò)后序序列發(fā)現(xiàn)根，找到其在中序序列的位置，從而在中序序列中發(fā)現(xiàn)左子樹(shù)和右子樹(shù)并獲得它們的長(zhǎng)度，最后在后序序列中找到對(duì)應(yīng)的左子樹(shù)和右子樹(shù)的后序序列。
這樣求某二叉樹(shù)的前序序列，變成了求該二叉樹(shù)左子樹(shù)的前序序列和該二叉樹(shù)右子樹(shù)的前序序列。

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

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

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

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

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

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

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

通過(guò)前序序列找到根，找到根在中序序列的位置，將樹(shù)分割成左右子樹(shù)，按照先右子樹(shù)再左子樹(shù)的順序找到子樹(shù)的根，直至子樹(shù)不可分割。先找到的根排在后找到的根的后面。
和推導(dǎo)前序序列，相比思路大致相同，實(shí)現(xiàn)細(xì)節(jié)上，找樹(shù)的根的方式不同，分割子樹(shù)的方式不同，保存根的方式不同。

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

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

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

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，求中序序列。

這是一道多解題。

推薦結(jié)合nodemon在node環(huán)境下學(xué)習(xí)算法。